[BOJ 12852] 1로 만들기 2
- 문제풀이
문제
정수 X에 사용할 수 있는 연산은 다음과 같이 세 가지 이다.
- X가 3으로 나누어 떨어지면, 3으로 나눈다.
- X가 2로 나누어 떨어지면, 2로 나눈다.
- 1을 뺀다.
정수 N이 주어졌을 때, 위와 같은 연산 세 개를 적절히 사용해서 1을 만들려고 한다. 연산을 사용하는 횟수의 최솟값을 출력하시오.
입력
첫째 줄에 1보다 크거나 같고, 106보다 작거나 같은 자연수 N이 주어진다.
출력
첫째 줄에 연산을 하는 횟수의 최솟값을 출력한다.
둘째 줄에는 N을 1로 만드는 방법에 포함되어 있는 수를 공백으로 구분해서 순서대로 출력한다. 정답이 여러 가지인 경우에는 아무거나 출력한다.
제한
| 시간 제한 | 메모리 제한 |
|---|---|
| 0.5sec | 512MB |
풀이
정수 $N$에 대하여 세 가지 연산을 적절히 사용하여 $1$을 만드는 최소 연산 횟수와 그 과정을 출력하는 문제다. 이전에 계산된 작은 숫자들의 최적해를 활용하여 큰 숫자의 최적해를 구할 수 있으므로 다이나믹 프로그래밍알고리즘을 적용하기 적합하다.
단순히 최소 연산 횟수만 구하는 것이 아니라 그 경로까지 출력해야 한다는 점이 핵심이다. 이를 위해 $DP$ 테이블을 구성할 때 각 숫자에서의 최소 횟수뿐만 아니라, 어떤 숫자에서 해당 최적해로 도달했는지(부모 노드)를 함께 기록해야 한다. 소스 코드에서는 구조체 ND를 정의하여 연산 횟수인 dp와 이전 숫자의 인덱스인 pre를 동시에 관리하였다.
임의의 숫자 $i$에 대하여 적용할 수 있는 점화식은 다음과 같다.
\[DP[i] = \min(DP[i/3], DP[i/2], DP[i-1]) + 1\]우선 $DP[i-1]$을 기본값으로 설정한 뒤, $i$가 $2$나 $3$으로 나누어떨어지는 경우 각각의 연산 결과가 현재 저장된 값보다 더 효율적인지 비교하여 최적해와 그 경로(pre)를 갱신한다.
$N$의 범위는 $1 \leq N \leq 1\,000\,000$이므로, $O(N)$의 시간 복잡도로 모든 숫자에 대한 최적해를 계산할 수 있으며 이는 제한 시간 $0.5$초 내에 충분히 수행 가능하다. 모든 계산이 끝난 후에는 $DP[N]$의 횟수를 출력하고, $N$부터 시작하여 pre 링크를 타고 역순으로 추적하며 숫자를 출력하여 경로를 복원한다.
소스코드
Github Link : Source Code
참고 알고리즘 : 다이나믹 프로그래밍