[BOJ] 1463. 1로 나누기

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

1463번: 1로 만들기

 

 

1. 해결방법

DP문제이다. 
본인은 DP로 해결해야할지 감은 왔지만 해결을 전혀 하지 못했다...

먼저 [0]을 N + 1만큼 리스트를 만들어준다.
[1], [2]의 값은 0, 1로 정해져 있으므로, 2부터 N + 1까지 for문을 돈다

i를 2부터 돌면서 dp[i]의 값을 dp[i - 1]에  + 1을 무조건 해주고, if문으로 2와 3으로 나누어 지는지 차례대로 비교해야한다.
물론 둘다 비교해야한다 비교해서 최솟값을 dp[i]에 갱신한다.

진짜 너무 어려웠다.... DP 공부가 많이 부족한 듯 하다.

 

 

2. 정답코드

import sys
input = sys.stdin.readline

N = int(input())
dp = [0] * (N + 1)

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

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

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

print(dp[N])