백준 1로 만들기 코드 및 해설 (파이썬)

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

1463번: 1로 만들기

 

나누고 빼는 대신 곱하고 더하는 것으로 바꿔 풀었다. N에서 1로 줄여나가는 것이 아니라, 1에서 N으로 늘려가는 것으로 방향을 반대로 보고 풀었다. 먼저 dp를 모두 N인 리스트로 초기화해주고, index 1의 값만 0으로 바꿔준다. 

1부터 N-1까지 다음을 반복한다.

현재 i에서 3 곱한 것이 N 이하면, graph[i]+1의 값과 graph[i*3] 중 최솟값 취하기 

현재 i에서 2 곱한 것이 N 이하면, graph[i]+1의 값과 graph[i*2] 중 최솟값 취하기 

현재 i에서 1 더한 것이 N 이하면, graph[i]+1의 값과 graph[i+1] 중 최솟값 취하기 

이후 dp 그래프의 마지막 원소인 N번째 index의 값을 출력해주면 된다.

 

import sys
N = int(sys.stdin.readline())
dp = [N] * (N+1)
dp[1] = 0

for i in range(1,N):
    if i*3 <= N:
        dp[i*3] = min(dp[i]+1, dp[i*3])
    if i*2 <= N:
        dp[i*2] = min(dp[i]+1, dp[i*2])
    if i+1 <= N:
        dp[i+1] = min(dp[i]+1, dp[i+1])

print(dp[-1])