백준-1463-1로 만들기

1. 문제 출처

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

1463번: 1로 만들기

2. 풀이

Dynamic Programming 방법 중 botton  up 방법을 사용하여 문제를 해결하였다. 

# 입력받기
import sys
n = int(sys.stdin.readline())
# 미리값을 저장할 배열
dp = [0] * (n+2)

# 1~3까지는 바로 출력한다.
if n==1:
    print(0)
elif n==2 | n==3:
    print(1)
else:
    dp[2] = 1
    dp[3] = 1
    for i in range(4, n+1):
        # 숫자가 i일 때 
        # 3가지 방법 중 최소 횟수인 방법을 사용하여 저장한다.
        dp[i] = min(
            dp[i-1],
            dp[int(i/2)] if i%2 == 0 else 1000001,
            dp[int(i/3)] if i%3 == 0 else 1000001
        ) + 1
    print(dp[n])