[백준] 1463 - 1로 만들기(동적프로그래밍) - (python 파이썬)

문제링크 : https://www.acmicpc.net/problem/1463

1463번: 1로 만들기

 

풀이과정:

dp를 처음접해서 사실 처음에는 그냥 큰 수(3->2->1)부터 나누고 빼고 하면 되는거 아닌가?

3으로 나누어 떨어지면 나누고 안되면 2로 나눠보고 안되면 1빼고 반복하면 되겠네 라고

생각했다가 혼났다... 동적 프로그래밍을 이용하는 문제이고, 처음 풀이를 보았을때,

한번에 이해가 되지 않았다.  핵심은 이 dp는 정확한 계산방법이 없으며 약간 브루트포스와

비슷한 방식으로 모든 경우에 대해 생각을 해보고 이것들의 최대값 또는 최솟값을 구한다.

dp[i] = dp[i-1] + 1

2와 3으로 나누어 떨어지지 않는 수에 대비하여 -1 해줄때 count를 해주는것이고,

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))

이들은 각각 2와 3으로 나누어질 때, 앞서 1을 뺄때가 dp[i]에 들어있기 때문에 이 중 최솟값을

찾는다. 3으로 나눌때 또한 앞에서 2로 나눌때의 결과가 dp[i]에 들어있기 때문에 이와 비교하면

문제가 없다.

 

 

전체코드

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

for i in range(2, N+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[N])

답(이미지)

 

후기: 알고리즘이 꽤 재밌고, 뒤에 나올 동적프로그래밍 여러 문제들이 궁금하다.