백준 DP 문제 - 1로 만들기 (파이썬)

https://www.acmicpc.net/problem/1463

1463번: 1로 만들기

 

1463번은 DP의 가장 기초적인 문제라고 했지만 어떻게 풀어야 할지 감도 못 잡겠어서 여러 블로그를 참고해 봤지만 역시 이해에는 영상이 최고인 것 같다는 생각이 듭니다.

저는 문어박사 IT편의점 님의 영상을 참고해서 공부했습니다.

마우스로 그린거라 많이... 엉망인 점 양해부탁드립니다.

1은 그냥 1이므로 따로 연산을 수행할 필요가 없으니 횟수는 0이 됩니다. 그럼 이제 2가 될 때는 +1과 *2와 *3인 경우를 봐야 합니다. 먼저 +1인 경우에는 x+1=2이므로 x는 1이 됩니다. 이때 1의 횟수와 현재 연산을 수행한 횟수 1을 더해서 1이 됩니다. *2인 경우에는 x*2=2는 x가 1이 될 때 이므로 1의 횟수 + 1해서 1이 됩니다. 2는 3으로 안 떨어지기 때문에 2가 되는 최소한의 횟수는 1이 됩니다.

다른 수들도 이와 같은 과정을 거쳐서 최종적으로 10이 1이 되는 횟수는 3이 됩니다.

이렇게 지난 과정의 값들을 기록해서 비교하는 풀이이므로 값을 저장할 배열이 필요합니다. 이때 1부터 N까지 값을 활용하므로 배열의 전체 크기는 N+1이 되어야 합니다. 초기값은 0으로 해서 배열을 생성하고 아래와 같은 코드를 구현합니다.

num = int(input())
dp = [0]*(num+1)

for i in range(2, num+1):
    dp[i] = 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)
print(dp[-1])

 

이렇게 문제를 해결할 수 있게 되었습니다. 덕분에 이해가 안되면 손으로 먼저 그려본 다음에 규칙을 찾으면 더욱 수월하게 문제를 풀 수 있다는 걸 깨닫게 되었습니다.