백준 알고리즘 - 1로 만들기 (1463번) [Python]

 

동적 계획법의 첫번째 예제로 조건은 세가지이다. 

 

문제 상황

- 경우의 수가 여러가지이고 그 중 최소가 되는 경우가 무엇인지 찾을 수가 없다.

- 모든 경우의 수를 무조건 검색하기에는 연산이 너무 많다. 

 

 

해결 전략

- 동적계획법을 써야한다는 사실은 알지만 적용 방법이 어려웠다.

- 검색을 통해 여러가지 코드를 참고하였고 그 중 Bottom-up 방식을 사용하는 것이 그나마 이해가 되었다. 

 

코드 

n = int(input()) # 숫자 입력
dp = [0,0,1,1] # 0과 1은 0번으로, 2와 3은 1번의 연산으로 1 가능
for i in range(4, n+1):
    dp.append(dp[i-1]+1)
    if i%2 ==0 :
        dp[i] = min(dp[i], dp[(i//2)]+1)
    if i%3 == 0:
        dp[i] = min(dp[i], dp[(i//3)]+1)  # 이게 elif면 틀린다.
print(dp[n])

 

해설

 

 

실수

- 2와 3으로 동시에 나누어지는 경우가 있는데 조건문을 elif로 처리하여 2의 배수일 때에는 3으로 나누어지는 경우를 계산하지 않게하여 작동하지 않았다. 

- dp[i]의 초기값을 넣을 때 i-1에서 1을 더하는 경우는 조건이 필요 없으므로 가장 위에 조건이 없이 넣는다는 생각을 하지 못했다.