[백준] 1463 - 1로 만들기 (Python)

문제 설명

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

1463번: 1로 만들기

---

문제 풀이

DP 개념 이해하고 연습문제 풀어보기!

 

1. 테이블 정의하기

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

 

2. 점화식 찾기

D[12] = ?

• 3으로 나누거나 (D[12] = D[4] + 1)
• 2로 나누거나 (D[12] = D[6] + 1)
• 1을 빼거나 (D[12] = D[11] + 1)

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

 

D[k]  = ? 

• 3으로 나누어지면 3으로 나누거나 (D[k] = D[k/3] + 1)
• 2로 나누어지면 2로 나누거나 (D[k] = D[k/2] + 1)
• 1을 빼거나 (D[k] = D[k-1] + 1) 

=> 이들 중 최솟값

 

 

3. 초기값 정의하기

• D[1] = 0

 

n = int(input())
d = [0] * (n + 1)

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

print(d[n])