[백준 1463] 1로 만들기 (DP 문제)

문제

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

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

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

입력

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

출력

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

예제

예제

힌트

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

---

나의 풀이

이 문제는 대표적은 DP 문제이다.

DP란 Dynamic Programming의 약자로 다음 조건을 만족하는 경우 DP를 사용해 문제를 풀이할 수 있다.

1. 큰 문제를 작은 문제로 나눌 수 있다.
2. 작은 문제에서 구한 정답이 그것을 포함하는 큰 문제에서도 동일하다.

DP를 이해하는데 가장 많이 사용하는 예제는 피보나치 수열 문제이다.

피보나치 수열은 Fibo(5) = Fibo(4) + Fibo(3) 과 같이 전형적으로 작은 문제로 나눌 수 있으며 작은 문제의 정답이 큰 문제에서 동일하게 적용되는 수열이다.

DP에는 하향식(Top-Down)과 상향식(Bottom-Up)이 있다.

하향식은 주로 재귀적인 방법을 사용하며 한 번 구한 결과를 메모해두는 방식인 메모이제이션(Memoization)을 사용하고,

상향식은 주로 반복적인 방법을 사용하며 결과를 저장하는 DP 테이블을 사용한다.

DP를 사용했을 때의 장점은 한 번 구한 문제는 다시 계산하지 않기 때문에 시간적인 효율성이 기하급수적으로 늘어난다는 것이다. DP를 사용하면 시간 복잡도가 O(N)이 된다. (피보나치 수열의 경우 DP를 사용하지 않으면 시간 복잡도가 O(N!) 이 된다. N!은 N 팩토리얼이다.)

x = int(input())
d = [0] * 1000001

for i in range(2, x+1):
    li = [d[i-1]]
    if i % 3 == 0:
        li.append(d[i//3])
    if i % 2 == 0:
        li.append(d[i//2])
    d[i] = min(li) + 1
print(d[x])

우선 사용자에게 숫자를 하나 입력받고, d라고 하는 리스트를 선언한다.d는 1,000,001개의 0으로 초기화 되는데, 이 문제에서 10^6 보다 작거나 같은 수가 주어진다고 했기 때문에 최대로 입력될 수 있는 수인 1,000,000을 모두 담기 위해서 (0 포함) 1,000,001의 크기로 리스트를 초기화 한 것이다.(d가 위에서 설명한 DP테이블이다)d에는 0~1,000,00 까지의 인덱스가 존재할텐데 만약 d[10] = 2라고 하면 그 값은 10을 1로 만드는데 두 번의 연산이 필요하다는 것을 의미한다.d[1]은 0이다. 왜냐하면 1 자체가 정답이기 때문에 연산을 할 필요가 없다.d[2]는 1이다. 왜냐하면 2는 2로 나누어 떨어지며 2로 한 번만 나누면 1이 되기 때문이다.d[3]도 1이다. d[2]와 같은 이유이다.d[4]는 2이다. 4는 2로 나누어 떨어지며 2로 나누면 2가 되는데, 이때 2가 1이 됄 때까지 몇 번의 연산이 필요한지 또 한 번 계산할 필요가 없다. 왜냐하면 d[2]에 이미 그 최솟값이 기록되어 있기 때문이다. d[2]에서 한 번의 연산만이 더 필요할 뿐이다....d[12]는 3이다. 12는 2와 3으로 모두 나누어 떨어지는데 이는 즉, d[11]과 d[6]과 d[4]에 한 번의 연산을 더 하면 되는 것이다. d[6]은 2이고, d[4]도 2이다. d[11]은 4이다. 이 셋 중 최소값인 2가 d[12]에 기록된다....d[n]은 d[n-1]과 n이 2로 나누어 떨어지면 d[n//2], 3으로 나누어 떨어지면 d[n//3] 이렇게 최대 3개의 값을 비교하여 가장 작은 값에 한 번의 연산을 더하기 위해 1을 더해준 값을 저장하면 되는 것이다.

d의 1,000,001개 요소를 모두 계산할 필요 없이 사용자에게 입력 받은 x까지만 계산하면 되기 때문에 반복문의 범위도 x+2까지로 설정하였다.

 

테스트 결과