[BOJ] 1463 1로 만들기 (Python3)

문제

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

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

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

입력

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

출력

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

예제

예제 입력 1
2

예제 출력 1
1

예제 입력 2
10

예제 출력 2
3

힌트

10의 경우에 10 -> 9 -> 3 -> 1 로 3번 만에 만들 수 있다.

문제 풀이

이 문제는 다이나믹 프로그래밍, 즉 동적계획법으로 푸는 문제이다. 사실 그동안 다이나믹 프로그래밍 문제는 솔직히 뭔말인지 잘 이해가 안되서 안풀고 있었는데, 이제 모든 유형을 번갈아가면서 풀 예정이라 오늘 다이나믹 프로그래밍부터 풀어보았다.

다이나믹 프로그래밍은 작은 문제들을 해결해감으로써 큰 문제를 해결하는 문제로, 가장 좋은 예로 피보나치 수열이 있다. 피보나치 수열의 경우 n번째 피보나치 수는 n-1의 피보나치 수와 n-2의 피보나치 수의 합으로, 이미 계산한 결과를 통해 다음의 결과가 나오는 방식이다. 이렇게 이전의 작은 문제들이 큰 문제를 해결하는데에 필요한 알고리즘을 다이나믹 프로그래밍이라고 한다.

이 문제의 경우는 N을 1로 만들기 위한 최소의 경우의 수를 출력하는 문제였는데, 맨처음에는 if와 elif 문으로 3과 2로 나눠지는 경우, 1을 빼면 3이나 2로 나누어 지는 경우로 구분해서 다이나믹이라기보다는 그리디하게 3우선으로 나눠지면 최소의 경우의수가 나올 것이라는 가정으로 풀었다. 하지만 이 문제는 모든 상황에서 동일하게 이러한 가정이 맞지 않으므로, 다이나믹 프로그래밍으로 풀어야 했다.

1 부터 차례대로 생각해보면, 3의 경우의 수는 3으로 나누는 경우 1일때, 4는 자연스럽게 3을 만들기 위해서 1을 빼고, 3으로나누는 경우의수 2가 된다. 따라서 뒤의 숫자는 2나 3으로 나누어 떨어지지 않는다면, 반드시 이전의 숫자의 경우의 수에서 1을 빼주는 경우의 수가 추가가 될 수 밖에 없다. 2나 3으로 나누어 떨어지는 경우에는, 그 수를 2,3으로 나눠서 나오는 수의 경우에 수에서 1을 더한 값이 그 수의 경우의 수가 될 것이다. 그럼 1을 빼고 나누었을 때의 경우의수와 바로 2나 3으로 나누었을때의 경우의 수중에서 작은 값을 해당 인덱스에 저장해주면 된다.

따라서 배열에 0부터 3까지의 경우를 넣어준뒤, N까지 순차적으로 각 숫자의 대한 최소 경우에 수를 찾아가며 N에 다다르면 1로 만들기 위한 최소 경우의 수를 찾을 수 있다.

코드

N = int(input())
dp = [0,0,1,1]

for i in range(4, N+1):
    dp.append(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])

10
3