백준 1463 파이썬 | 1로 만들기

코드

from sys import stdin
input = stdin.readline

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

for i in range(4, n+1):
    cnt1 = 999999
    cnt2 = 999999
    cnt3 = 999999
    if (i / 2).is_integer():
        cnt2 = dp[i // 2] + 1
    if (i / 3).is_integer():
        cnt3 = dp[i // 3] + 1
    cnt1 = dp[i-1] + 1
    dp.append(min(cnt1, cnt2, cnt3))
print(dp[n])

설명

고민을 오래 했던 문제이다. 처음에는 3으로 최대한 나눠야 숫자가 빠르게 작아지지 않을까 생각했는데 그렇지 않았다.

동적 프로그래밍으로 문제를 풀려고 봐봤다. dp[N]의 값이 연산의 최솟값이 되게 했다. N이 1일 때 2일 때 3일 때 4일 때 5일 때... 를 생각해 보면 최소 연산의 수는 앞의 계산 결과에 의존적이었다. N = 1, 2, 3의 경우에는 명확하게 답이 0, 1, 1 이다. N=4일 때는 2로 나누면 2가 되어 dp[2] + 1 =  2가 최솟값이다. 또는 빼기 1을 해서 3으로 만든 다음 dp[3] + 1 = 2로 할 수도 있다. 이렇게 하나씩 해보면 dp[n]의 값은 그 이전의 결과에 의존적이라는 것을 알 수 있다.

 

할 수 있는 연산은 세 가지 경우가 있다.

 

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

2. X가 2로 나누어 떨어지면, 2로 나눈다.

3. 1을 뺀다.

 

N이 10일때의 경우처럼 무조건 나누기를 먼저 하는 것이 연산의 최소값을 보장하지 않는다. 10의 경우에는 먼저 1을 빼는 것이 최솟값이다. 그래서 세 가지 경우에 대한 연산의 최솟값을 dp를 이용해 모두 찾은 다음 그 중 가장 작은 값이 연산의 최솟값이 되는 것이다.

 

메모리: 37448 KB

시간: 900 ms

문제

https://www.acmicpc.net/problem/1463

1463번: 1로 만들기