[다이나믹 프로그래밍] 1로 만들기 - 파이썬(python)

1로 만들기

난이도 : 中下 풀이 시간 : 20분

시간 제한 : 1초 메모리 제한 : 128 MB

 

---

 

해답

 

x = int(input())

dp = [0] * 30001

for i in range(2 , x+1):
    dp[i] = dp[i-1] + 1

    if i % 2 == 0:
        dp[i] = dp[i//2] + 1
    if i % 3 == 0:
        dp[i] = dp[i//3] + 1
    if i % 5 == 0:
        dp[i] = dp[i//5] + 1

print(d[x])

---

예시

 

# 정수 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])

---

해설

 

처음에는 단순 구현 문제라고 생각했지만, 점화식을 이용한 다이나믹 프로그래밍으로 푸는 문제였습니다.
점화식으로 표현해보면 a[i] = min(a[i/5], a[i/3], a[i/2], a[i-1]) 이므로 이를 코드로 작성하면 됩니다.