[Pyhton/코테] 백준 1463 1로 만들기

1463 1로 만들기

문제 및 조건 설명: https://www.acmicpc.net/problem/1463

알고리즘 설계

💡Idea.

최소 횟수 즉 최단 거리를 구하는 것으로 BFS를 사용할 수도 있지만 해당 풀이에서는 DP 를 사용한다.

 

🎲Step.

1. 테이블 정의하기

D[i] = i 를 1로 만들기 위해 필요한 연산 사용 횟수의 최소값

2. 점화식 찾기

ex) D[12] = ?

→ D[1] , .. D[11]의 모든 값을 알고 있는 상황. 

→ 가능한 연산은 세 가지

D[12/3] = D[4]+1
D[12/3] = D[6]+1
D[12]-1 = D[11]+1

즉, D[12]를 1로 만들기 위해서는

D[12] = min(D[4]+1, D[6]+1, D[11]+1)

점화식: D[k] = ?

D[k/3] = D[k/3]+1
D[k/3] = D[k/2]+1
D[k]-1 = D[k-1]+1

3. 초기값 정의하기

D[1] = 0

 

알고리즘 구현

d = [0] * 1000005
n = int(input())

d[1] = 0
for i in range(2, n+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)

print(d[n])