해킹왕 양선규

x = int(input()) d = [0] * ((10 ** 6) + 1) for i in range(2, x + 1): d[i] = d[i - 1] + 1 if i % 2 == 0: d[i] = min(d[i], d[i // 2] + 1) if i % 3 == 0: d[i] = min(d[i], d[i // 3] + 1) print(d[x]) 다이나믹 프로그래밍 문제이다. d는 메모이제이션(값을 저장해 놓을)할 리스트. i는 현재 계산중인 숫자 d[i] 는 i에 대한 최소연산횟수이다. 숫자 2부터 바텀 업 방식으로 d리스트를 채워나가 최종적으로 x의 최소연산횟수를 구하는 것이다. 이 문제는 3가지 연산을 할 수 있다. 1을 빼기, 2로 나누기, 3으로 나누기 하지만 2나 3으로 나눠진다고 해서 무조건..

DP(Dynamic Programming, 동적 계획법) - 하나의 큰 문제를 여러 개의 작은 문제로 나누어서 그 결과를 이용해, 다시 큰 문제를 해결할 때 사용한다. - DP는 특정 알고리즘이 아니라 하나의 방법론이므로 다양한 문제해결에 쓰인다. - “큰 문제를 작은 문제로 쪼개서 그 답을 저장해두고, 재활용” - DP라는 이름은 그냥 멋있어 보여서 지은 이름이다. DP를 쓰는 이유 - 일반적인 재귀방식도 DP와 유사하지만, 일반적인 재귀를 단순히 사용 시 “동일한 작은 문제가 반복”되어, 비효율적인 계산이 될 수 있다. ex) 피보나치 수열. 한번 한 계산을 또 하고 또 하고 반복한다. --->>> DP 방식으로 작은 문제의 결과를 저장해두고 “재사용”하면 매우 효율적으로 해결할 수 있다. --->>..