백준 (boj) 파이썬 - 1463 : 1로 만들기 (DP)

문제 링크 : https://www.acmicpc.net/problem/1463

1463번: 1로 만들기

 

 

---

문제 분류 : 다이나믹 프로그래밍

https://infinitt.tistory.com/246

알고리즘 - 다이나믹 프로그래밍 (Dynamic Programming)

 

처음엔 당연스럽게 조건문을 통해 구현했다. (n//3 , n//2 , n-=1 순서대로).

하지만 문제의 테스트케이스인 10이 반례였다.

즉, 단순히 조건문으로 풀게되면 10 - > 5 -> 4 -> 2 -> 1 이지만, 사실 10은

10 -> 9 -> 3 - > 1 으로, n/3보다 n-1을 먼저 해줘야 최소값이 나오게 된다.

 

따라서 이 문제는 단순 구현이 아니라, 다이나믹 프로그래밍으로 풀어야 한다.

 

 

• N이라는 수는 N//3을 연산전으로 돌리면, 즉 +1을 하면 만들 수 있다.
• N이라는 수는 N//2을 연산전으로 돌리면, 즉 +1을 하면 만들 수 있다.
• N이라는 수는 N-1을 연산전으로 돌리면, 즉 +1을 하면 만들 수 있다.

따라서 !!! 점화식 : dp(N) = min ( dp(N//3) +1, dp(N//2)+1 , dp(N-1)+1 )

 

 

*정답 코드 (Python)

n = int(input())

dp = [0 for _ in range(n+1)]

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

    if i%2 == 0 and dp[i] > dp[i//2] + 1 :
        dp[i] = dp[i//2]+1
        
    if i%3 == 0 and dp[i] > dp[i//3] + 1 :
        dp[i] = dp[i//3] + 1
        
print(dp[n])

 

• n+1개만큼의 0으로 이루어진 배열을 만들어준다.
• dp라는 배열의 index는 문제의 입력n과 대응하고, index의 값은 연산최솟값(문제의 출력)에 대응하게된다.

 

* 시간복잡도

배열의 크기 * O(1)이다. (배열 하나당 O(1)의 시간복잡도를 가지므로)

배열은 n+1이므로 시간복잡도는 O(n)