[DP] 백준 1463. 1로 만들기

클릭하면, 백준 문제로 연결된다

 

 문제 요구사항 

정수 X를 1로 만들기 위한 연산이 3가지가 있다. 이를 적절히 사용하여 1로 만들고자 할 때, 최소한의 연산 횟수를 구하라

 

 주의사항과 DP의 특징 

어떤 N에 대해 나올 수 있는 모든 연산의 횟수를 구하면, 이 문제는 시간초과가 뜬다. N보다 작거나 N을 2나 3으로 나눴을 때의 small N들이 최소한의 연산횟수로 도출된 것을 이용해 N의 최소연산횟수를 구하게 되면, 훨씬 시간자원을 아낄 수 있다.

small N들은 문제에서 제시한 연산 방법에 따라 2나 3을 나눈 수, -1을 한 수들이다. 예를 들어 6의 최소연산횟수를 구하고자 할 때, N = 6이고, small N들은 2,3,5가 된다. 2,3,5를 만들 때 사용했던 연산에 각각 *3, *2, +1을 하게 되면 6을 만들 수 있으므로, 2, 3, 5의 연산횟수에 +1 만 해주면 6의 최소 연산횟수를 구할 수 있는 것이다.

 

DP는 이처럼 약간은 그리디를 풀 때처럼 접근하되, 이전 연산 결과를 활용해 bottom up 혹은 top down 방식으로 정답을 도출하기 때문에 점화식의 사용이 핵심이다. 이러한 점화식의 규칙을 찾아내기 위해서 계산이 쉬운 값들을 일일이 대입해 이전 값들과의 관계성을 빠르게 찾아내야 한다.

 

 코드 이해하기 

 

n = int(input())

dp = [0] * (n+1)

for i in range(2, n+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[n])

 

 

 

 

 다른 분들의 코드를 보면, 이 문제는 주로 bottom up방식으로 풀려있다. N까지 도달하기 위해 작은 수부터 차례로 값을 채워나가고, 값을 채울 때 min 함수를 사용해 최소 횟수를 보장한다. index가 N들에 해당하고 배열의 값들은 각 N들의 최소 횟수들로 채워진다는 점을 명심해야 한다. (가장 이해가 어려웠던 부분)

 

+ 빼기 일 연산 '-1' 에 대해 다른 연산과 다르게 진행하는데, 우선 빼기일 연산을 d[N]에 넣고, 이후에 2의 배수이거나 3의 배수일 경우, 값들을 대체해 나감으로써 min(A, B, C) 세가지 연산에 대한 최소값을 취하게 한다.

 

 문제보고 패턴 익히기 

DP 마인드맵

 

(DP 포스팅)

https://namnamiroo.tistory.com/44

[DP 다이나믹 프로그래밍] 코드 패턴과 특징 - ing