문제
정수 X에 사용할 수 있는 연산은 다음과 같이 세 가지 이다.
X가 3으로 나누어 떨어지면, 3으로 나눈다.
X가 2로 나누어 떨어지면, 2로 나눈다.
1을 뺀다.
정수 N이 주어졌을 때, 위와 같은 연산 세 개를 적절히 사용해서 1을 만들려고 한다. 연산을 사용하는 횟수의 최솟값을 출력하시오.
입력
첫째 줄에 1보다 크거나 같고, 106보다 작거나 같은 정수 N이 주어진다.
풀이
dynamic programming으로 풀기 위해 점화식을 만드는 것이 관건이었던 문제.
1부터 시작하기 때문에, 1에서 0으로 시작하기 위해 (만들고자 하는 목표가 1, 즉 1은 더이상 연산이 필요 없기 때문에 0으로 시작한다) 0번째에 -1을 넣고 시작.
총 3가지 연산이 가능하다.
- -1연산
- / 2 연산
- / 3 연산
세 가지 연산 중 어느 것이 빠른지는, 직접해보기 전까지 증명할 방법이 없다.
ex) 10 = 2 * 5 이기 때문에 2로 나뉘니까 더 빠른거 아니야? 생각할 수 있지만, -1을 하게 되면 9이다. 2로 나눈 후에는 총 5번의 연산 / -1 이후 3으로 나누는 것은 3번의 연산만을 필요로 한다.
따라서, 어쩔 수 없이 bottom-up 방식으로, 1씩 더해가며 어느 것이 가장 뛰어난지 업데이트한다.
가장 최소로 만들 수 있어야되기 때문에, 2 혹은 3으로 나뉘게 될 경우, 현재 저장돼 있는 값 (+1씩 업데이트 해주므로 미리 0이 아닌 값이 들어가있다)과 나누기 가능한 값 중 min값으로 업데이트해준다.
ex2) dp[n] = dp[n-1] + 1 로 값을 먼저 업데이트, 만약 n%3==0 이라면 {(n/3) * 3} 연산이 더 빠를 것이다. (즉, 1을 구하기 위해 n / 3 연산을 진행하는 것이 빠를 것이라는 소리) 그렇기에 min(dp[n/3] + 1, dp[n])을 비교하여 더 작은 값으로 업데이트 하는 것이다 (이 때의 dp[n]은 dp[n-1] + 1로 이미 업데이트된 값)
코드
import sys
input = sys.stdin.readline
i = int(input())
dp = [0 for _ in range(i+1)]
dp[0] = -1
a = 1
while a<=i:
dp[a] = dp[a-1] + 1
if a%3==0:
dp[a] = min(dp[a], dp[int(a/3)] + 1)
if a%2==0:
dp[a] = min(dp[a], dp[int(a/2)] + 1)
a+=1
print(dp[i])