[백준/파이썬]1463 1로 만들기

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

1463번: 1로 만들기

 

문제

 

n을 입력받고

 

1 빼기

2로 나누기

3으로 나누기

 

이 3가지를 가장 적게 사용해 1로 만드는 문제이다.

 

DP공부하면서 처음 푼 문제인데 이해하기가 정말 어려웠다.

 

n=5라고 했을 때

 

(d[1]은 0으로 초기화되어 있다.)

 

d[2]

• d[2-1] + 1 = 1
• d[2/2] + 1 = 2
• d[2/3] + 1 = 불가능

초록색 값이 가장 작으므로 d[2]의 값은 1이다.

그럼 지금까지 d는

[0, 0, 1]

 

d[3]

• d[3-1] + 1 = 2
• d[3/2] + 1 = 불가능
• d[3/3] + 1 = 1

이것도 가장 작은 1이 d[3]의 값이 된다.

d = [0, 0, 1, 1]

 

d[4]

• d[4-1] + 1 = 2
• d[4/2] + 1 = 2
• d[4/3] + 1 = 불가능

가장 작은 2가 d[4]의 값이 된다.

d = [0, 0, 1, 1, 2]

 

d[5]

• d[5-1] + 1 = 3
• d[5/2] + 1 = 불가능
• d[5/3] + 1 = 불가능

가장 작은 3이 d[5]의 값이 된다.

d = [0, 0, 1, 1, 2, 3]

 

마지막으로 d[5]를 출력해 주면 3이 출력되게 된다.

 

이걸 코드로 하면 된다.

 

정답

num = int(input())
dp = [0 for i in range(0, num+1)]

for i in range(2, num+1) :
    dp[i] = dp[i-1] + 1

    if i % 2 == 0 :
        dp[i] = min(dp[i], dp[i//2]+1)
    if i % 3 == 0 :
        dp[i] = min(dp[i], dp[i//3]+1)

print(dp[num])

 

---

dp문제 많이 풀어봐야겠다..