[Dynamic Programming] 1로 만들기

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

1463번: 1로 만들기

 

def solution(x):
    for i in range(2, x + 1):
        d[i] = d[i - 1] + 1
        if i % 2 == 0:
            d[i] = min(d[i], d[i // 2] + 1)
        if i % 3 == 0:
            d[i] = min(d[i], d[i // 3] + 1)
    return d[x]


d = [0] * 1000000
x = 10

print(solution(x))	# 3

DP 테이블인 리스트 d를 10^6만큼 초기화합니다.

그리고 사용 가능한 연산 기능 세 가지 중 가장 작은 값(최소 연산 값)을 d[i]에 저장합니다.

이러한 방법은 최적 부분 구조를 가지기 때문에 다이나믹 프로그래밍으로 풀 수 있습니다.

 

따라서  i를 2부터 x까지의 모든 d[i]에 대하여 최소 연산 수를 가지게 되기 때문에 d[x]는 세 가지 연산 조합의 최소 횟수가 됩니다.