단순 그리디 방식으로 푸는 것이 아니라 10->9->3->1 처럼 1을 빼고나서 3을 나눴을 때 더 빠르게 1로 만들 수 있기 때문에 동적계획법으로 접근하면서 메모이제이션 기법을 사용해야 한다.
n = int(input())
dp = [0 for _ in range(n+1)]
for i in range(2, n+1):
dp[i] = dp[i-1]+1
if i%3 == 0:
dp[i] = min(dp[i], dp[i//3]+1)
if i%2 == 0:
dp[i] = min(dp[i], dp[i//2]+1)
print(dp[n])
1. 왜 dp 리스트를 n+1까지 0으로 만드는가?
예를 들어서 n이 10이라고 했을 때 dp[10]까지 최소값을 저장하면서 연산할 것이기 때문에 리스트에 +1을 더해야 한다.
2. for i in range(2, n+1)에서 왜 2부터 시작인가?
예로 생각해보면 이해가 쉽다. n이 2일 때 1로 빼던 2로 나누건 1로 만들기 위해 과정은 단 1번이다.
그렇다면 dp[2]에는 1이 저장되어야 한다.
그래서 dp[2] = dp[1] + 1 을 통해 dp[2] = 1이 된다.
3. 이제 밑에 설명을 해보자.
for 바로 아래 문장으로 dp[10]에 dp[9]에다가 1을 더한 값이 있다고 가정해보자.
10은 i%2 == 0에 속하기 때문에 dp[10] = min(dp[10], dp[5]+1)과정으로 오게 되는데
dp[10]은 dp[9]에다가 1을 더한 과정이 dp[5]+1 과정보다 더 적은 수이기 때문에
min(dp[i])가 결과값으로 나오게 된다.
이해가 잘 되지 않는다면 잘 설명되어 있는 블로그가 있으니 아래 블로그를 참고하자.
댓글