[Algorithm] 백준 #1463 1로 만들기

 

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

1463번: 1로 만들기

 

DP를 사용해서 푸는 문제이다. 

N을 1로 만들기 위해 필요한 최소 횟수는 N-1을 1로 만들기 위한 최소횟수 + 1 OR 2나 3으로 나누어지면, 나눠지고 남은 몫에 +1하는 횟수이다. 

 

# 1463 1로 만들기
import sys
input = sys.stdin.readline

N = int(input())
dp = [0] * (N+1)  # dp리스트를 모두 0으로, N+1개만큼 초기화 시켜준다.

for i in range(2, N+1):
    dp[i] = dp[i - 1] + 1
    if i % 3 == 0:  # 3으로 나누어 떨어질 때 최솟값을 저장
        dp[i] = min(dp[i // 3] + 1, dp[i])
    if i % 2 == 0:  # 2로 나누어 떨어질 때 최솟값을 저장
        dp[i] = min(dp[i // 2] + 1, dp[i])
print(dp[N])