[DP 알고리즘] 1로 만들기 S3

기출 : BOJ #1463

 

DP는 다음 조건을 만족할때 사용한다

 

1. 큰 문제를 작은 문제로 나눌 수 있다 (점화식 정의 가능)

2. 작은 문제에서 구한 답이 큰 문제에서도 사용된다

 

만약 DP로 해결해야 한다는 생각을 했다면

DP의 문제풀이 순서는 다음과 같다

 

1. 점화식 정의하기

2. 범위 설정하기(초기값, 계산할 범위)

 

이 문제에서 점화식은 다음과 같다

 

D[n] = n을 1로 만드는 최소 연산의 수

D[n] = min(D[n-1]+1, D[n//2]+1, D[n//3]+1)

 

다음으로 초기값은 D[1]=0, 계산할 범위는 2~n 이다 

 

# 점화식 정의
# D[n] : n일때 1을 만드는 최소 연산 횟수
# D[n] = min(D[n-1], D[n//2], D[n//3])
# D[1] = 0
# D[2] = 1

n = int(input())
d = [0 for _ in range(n+1)]

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

print(d[n])