[Python/DP] 1463 1로 만들기 (어려움)

문제

정수 X에 사용할 수 있는 연산은 다음과 같이 세 가지 이다.

1. X가 3으로 나누어 떨어지면, 3으로 나눈다.
2. X가 2로 나누어 떨어지면, 2로 나눈다.
3. 1을 뺀다.

정수 N이 주어졌을 때, 위와 같은 연산 세 개를 적절히 사용해서 1을 만들려고 한다. 연산을 사용하는 횟수의 최솟값을 출력하시오.

 

입력

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

출력

첫째 줄에 연산을 하는 횟수의 최솟값을 출력한다.

입력 예시	출력 예시
2	1
10	3

---

풀이

전의 결과를 다음 결과에 이용하게 되는. 점화식을 활용한 DP 문제

그리디로 문제를 푼다면 당연히 큰 수로 처음부터 계속 나누는 것이 제일 빨리 1로 도달할 수 있을 것이다.

하지만, 10의 경우엔 10 - 5 - 4 - 2 - 1로 푸는 방법 보다,

처음부터 1을 빼고 10 - 9 - 3 - 1을 만드는 방법이 최솟값이다. 예상을 벗어난 것 이다!

그렇기에 동적 계획법을 이용한다.

동적 계획법으로 1을 빼는 경우, 2로 나누는 경우, 3으로 나누는 경우 모든 경우의 수 중 최솟값을 찾아낼 수 있기 때문이다.

 

또한 동적 계획법은 메모이제이션 방법을 사용해 중복해 계산되는 값을 저장해 효율을 높여준다.
(앞에서 구한 결과값을 저장하였다가 후에 사용)

출처

 

 

list에 저장하는 값이 인덱스 n에 대해 n을 1로 만드는 최소 연산의 수

- n이 1일 때는 이미 1이므로 연산이 필요하지 않다. 즉 d[1] = 0이다. 따라서 코드에선 for문을 돌 때 시작점을 2로 잡았다.
- n이 2일 때는 2로 나누어 떨어지므로 바로 2/2를 진행하고 나면 값은 1이 된다. 2가 1이 되기까지는 1번의 연산을 필요로 하므로 d[2] = 1이다.
- n이 3일 때 역시 3으로 나누어지므로 바로 3/3을 진행하고, 값은 1이 된다. 3이 1이 되기까지는 1번의 연산이 필요하므로 d[3] = 1이다.
- n이 4일 때는 4 / 2 -> 2 / 2 = 1, 총 2번의 연산을 진행하였으므로 d[4] =2 가 된다.
- n이 5일 때는 2나 3으로 나누어지지 않으므로 -1을 진행한다. 5-1 -> 4 / 2 -> 2 / 2 = 1로, 총 3번의 연산을 진행하여 d[5] = 3이 된다.
- n이 6일 때는 2와 3 모두로 나누어진다. 두 방법 모두 해보자. 6 / 3 -> 2 / 2 = 1, 6 / 2 -> 3 / 3 = 1 이므로, 처음에 2로 나누던 3으로 나누던 모두 2번의 연산을 필요로 한다. 즉, d[6] = 2가 된다.
- n이 7일 때는 2와 3 모두 나누어지지 않으므로 -1을 진행한다. 그러면 값은 6이 되고, 6은 또 다시 2와 3 모두로 나누어진다. 두 방법 모두 진행하더라도 6 / 3 -> 2 / 2 = 1 , 6 / 2 -> 3 / 3 = 1 이므로, n[7] = 7 - 1 -> 6 / 3 -> 2 / 2 = 1 혹은 7 - 1 -> 6 / 2 -> 3 / 3 = 1 로, 3번의 연산을 필요로 하여 d[7] = 3이 된다.


위 연산의 나열을 천천히 읽어보면 부분 문제들이 보인다.
예컨데, n이 7일 때 n에서 1을 빼고나면 6이 되고, 6을 1로 만드는 연산은 n이 6일 때의 연산 값과 같다.
다시 말해, n이 7일 때는 n에서 1을 빼는 연산 횟수 1번과, 6을 1로 만드는 d[6] 값을 더하면 d[7] 값을 구할 수 있다.
이것을 식으로 표현하면 d[7] = 1 + d[6]가 될 것이다.

n이 6일 때도 보자. n을 2로 나누고 나면 n은 3이 되고, 3을 1로 만드는 연산횟수는 d[3]이다.
즉, n이 6일 때는 n을 2로 나누는 연산 횟수 1번과 3을 1로 만드는 d[3] 값을 더하면 d[6] 값을 구할 수 있다.
이것을 식으로 표현하면 d[6] = 1+ d[6//2] 이 되는 것이다.
물론 n을 처음에 2가 아닌 3으로 나누면 d[6] = 1 + d[6//3]이 될수도 있다. 이럴 땐, 두 값을 비교해 더 작은 값을 d[6]에 삽입해주면 된다.

이런 식으로 for문을 돌면서 n을 우리가 입력받은 값까지 돌게 되면 d[n]에는 n번째 값을 1로 만드는 최소 연산 횟수를 구할 수 있게 되며, 이 때의 시간복잡도는 O(n)에 이른다.

출처

 

 

n = int(input())
d = [0]*(n+1) #1부터 n까지

#d가 i-1번째까지 이미 채워져있다고 생각
for i in range(2, n+1):
    d[i] = d[i-1] + 1 
    # n이 1까지 도달하는 데 걸리는 갯수는 증가해야함 
    # (option 실행후 값이 아니기 때문에 안 줄어듦)
    
    if i%3 == 0:
        d[i] = min(d[i], d[i//3] +1)
    if i%2 == 0:
        d[i] = min(d[i], d[i//2] +1)

print(d[n])