본문 바로가기
  • 질문, 댓글, 지적 전부 환영입니다! 감사합니다
백준 알고리즘

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

by Newmon 2020. 4. 23.

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

 

1463번: 1로 만들기

첫째 줄에 1보다 크거나 같고, 106보다 작거나 같은 정수 N이 주어진다.

www.acmicpc.net

 

 


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

https://infinitt.tistory.com/246

 

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

다이나믹 프로그래밍 (Dynamic Programming) : DP 개념 : 문제를 더 작은 단위로 쪼개어 해결하는 알고리즘. (분할 정복 알고리즘과 비슷하다. 차이점은 바로 아랫줄.) 핵심은, 그 작은 단위의 문제들이 반복해서..

infinitt.tistory.com

 

처음엔 당연스럽게 조건문을 통해 구현했다. (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)

 

댓글0