1로 만들기

이 문제는 이것이 코딩테스트다. 217페이지 문제이다.

문제 난이도는 높지 않았다.

아래는 나의 코드이다.

import sys

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

dp[1]=0
dp[2]=1

for i in range(2,N+1):
    temp = [N] * 4
    if i%5 == 0:
        temp[0] = dp[i//5] + 1
    if i%3 == 0:
        temp[1] = dp[i//3] + 1
    if i%2 == 0:
        temp[2] = dp[i//2] + 1
    temp[3]=dp[i-1]+1
    dp[i]=min(temp)

print(dp[N])

 

 

아래는 예시코드

# 정수 X를 입력 받기
x = int(input())

# 앞서 계산된 결과를 저장하기 위한 DP 테이블 초기화
d = [0] * 1000001

# 다이나믹 프로그래밍(Dynamic Programming) 진행(보텀업)
for i in range(2, x + 1):
    # 현재의 수에서 1을 빼는 경우
    d[i] = d[i - 1] + 1
    # 현재의 수가 2로 나누어 떨어지는 경우
    if i % 2 == 0:
        d[i] = min(d[i], d[i // 2] + 1)
    # 현재의 수가 3으로 나누어 떨어지는 경우
    if i % 3 == 0:
        d[i] = min(d[i], d[i // 3] + 1)
    # 현재의 수가 5로 나누어 떨어지는 경우
    if i % 5 == 0:
        d[i] = min(d[i], d[i // 5] + 1)

print(d[x])