(Python)[DP] 1로 만들기

본 글은 “이것이 취업을 위한 코딩 테스트다 with 파이썬” 교재를 참고한 것임

문제

풀이

작은 문제에서 구한 답이 큰 문제에서 그대로 사용될 수 있을 것 같기 때문에 DP를 떠올렸다.

탑다운 보다는 보텀업 방식으로 구현하는 것이 좋다고 하여 보텀업 방식으로 코드를 구현한다.

소스코드

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

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

# DP 진행(보텀업)
for i in range(2, x+1):
    # 현재의 수에서 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])