1463번 Python

과거에 풀어봤던 문제긴한데 역시 제대로 이해하지 않고 급하게 넘어간 느낌이라 처음부터 다시 풀어보고 있다.

 

1로 만들기

문제는 가장 최적의 해로 주어진 수를 1로 만드는 문제이다. 총 3가지의 연산이 있다. 이를 그리디로 풀었을 경우에는 10을 넣었을 때 4가 나와 오답이 발생한다. 이는 최적의 수를 구하는 것이 아닌 눈 앞에 보이는 가장 탐욕적인 방법으로 풀었기에 최적의 해를 구할 수 없었기 때문이다.

 

모든 경우의 수를 다 대입해서 해결해야하는 DP 문제이다. 나는 가장 먼저 점화식을 어떻게 만들지 생각해봤다.

 

2 -> 1
3 -> 1
4 -> 2 -> 1
5 -> 4 -> 2 -> 1
...

최적의 해를 구하면 다음과 같이 구할 수 있다. 자세히 보면 규칙이 보인다.

 

2 -> 1 # d[2] = 1
3 -> 1 # d[3] = 1
4 -> 2 -> 1 # d[4] = d[2] + 1
5 -> 4 -> 2 -> 1 # d[5] = d[4] + 1
...

이걸 통해서 이제 문제에서 제시하는 3가지의 계산을 모두 적용하는 식으로 가보자. 하지만 당최 어떻게 코드를 짜야하는지 감이 안왔다. 보고 또 이해하려고 노력해 얻은 결과값은 다음과 같았다.

 

import sys

n = int(sys.stdin.readline())
dp = [0] * 1000001

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])

사용한 DP는 bottom-up 방식이다. 아래에서부터 순차적으로 올라가기에 반복문을 사용했다.

 

1. dp 배열을 1000001번 곱한 이유 : 문제에서 10의 6제곱까지라고 나와있다. 또한, 인덱스는 0번부터 시작임을 감안해 1번 더 곱하여 1은 1번의 인덱스에서 시작하는 것처럼 혼돈하지 않기 위함이다.

 

2. 배열을 2번부터 시작한 이유 : 1은 어차피 항상 1이기 때문에 횟수는 0번이다. 따라서 2번부터 n까지 최적의 해를 메모이제이션하기 위해 시작한다.

 

3. dp[i] = dp[i-1] + 1의 의미 : dp[3]에서 1을 빼면 무엇이 나올지 생각해보자. dp[3] - 1 = dp[2]가 된다. 즉, dp[3] = dp[2] + 1이 되어 dp[i] = dp[i-1] + 1로 정확한 의미는 1을 빼는 과정이라 생각하면 된다. 이전의 해에서 1을 한 번 뺏기에 위의 문제에서 제기하는 횟수 한 번을 추가하는 것이다.

 

4. min()으로 구분하는 이유 : 반복문으로 메모이제이션 해를 구하는 식에서 2나 3으로 나누어 떨어지는 경우는 i에서의 반복문 안에 정의했던 값이 나누어 떨어진 해에서 1을 더한 것 중 가장 작은 것을 dp[i]에 초기화한다.

 

2 -> 1 # d[2] = 1
3 -> 1 # d[3] = 1
4 -> 2 -> 1 # d[4] = d[2] + 1
5 -> 4 -> 2 -> 1 # d[5] = d[4] + 1
...

이 식에서 보이는 것처럼 d[4] = d[2] + 1 -> d[i] = d[i // 2] + 1이 바로 그 형태이다.