문제
정수 N이 주어졌을 때 아래 세 연산을 사용하여 1로 만드는 최소 연산 횟수와 그 과정을 출력하는 문제이다.
- N이 3의 배수이면 3으로 나눈다.
- N이 2의 배수이면 2로 나눈다.
- N에서 1을 뺀다.
BOJ 1463(1로 만들기)의 확장 버전으로, 최소 횟수뿐만 아니라 실제 과정의 수열도 출력해야 한다.
입력
첫째 줄에 N이 주어진다. (1 ≤ N ≤ 1,000,000)
출력
첫째 줄에 최소 연산 횟수를 출력한다. 둘째 줄에 과정에서 거치는 수를 공백으로 구분하여 출력한다.
예제
| 입력 | 출력 |
|---|---|
2 | 1 2 1 |
10 | 3 10 9 3 1 |
풀이
바텀업 DP로 1부터 N까지 최소 연산 횟수를 채우고, path[i]에 i에서 이전 상태를 기록하여 역추적으로 경로를 복원한다.
d[i]: i를 1로 만드는 최소 연산 횟수.d[1] = 0으로 초기화하고 나머지는MAX_VALUE로 설정한다.path[i]: i에서 이전 단계의 값을 기록한다. 경로 역추적에 사용한다.- i = 2부터 N까지 순회하며 세 연산을 각각 적용한다.
- i가 3의 배수:
d[i/3] + 1 < d[i]이면d[i] = d[i/3] + 1,path[i] = i/3 - i가 2의 배수:
d[i/2] + 1 < d[i]이면d[i] = d[i/2] + 1,path[i] = i/2 - 1 빼기:
d[i-1] + 1 < d[i]이면d[i] = d[i-1] + 1,path[i] = i-1
- i가 3의 배수:
d[N]을 출력한 뒤,N부터path[N]을 따라가며 0이 될 때까지 출력한다.
핵심 아이디어: DP 테이블과 함께 path 배열을 유지하여 역추적을 구현한다. 각 상태 i에서 "어디서 왔는가"를 기록해두면, 최종 상태에서 시작 상태까지 링크를 따라가며 경로를 복원할 수 있다. 세 가지 연산 중 최솟값을 택하는 순서에 유의한다.
코드
package com.ssafy.an.day099;
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.Arrays;
public class Day64BOJ12852일로이만들기 { // 12852 1로 2만들기
static int N;
static int[] d, path;
public static void main(String[] args) throws Exception {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringBuilder sb = new StringBuilder();
N = Integer.parseInt(br.readLine());
d = new int[N + 1];
path = new int[N + 1];
Arrays.fill(d, Integer.MAX_VALUE);
d[1] = 0;
for (int i = 2; i < N + 1; i++) {
if (i % 3 == 0)
divThree(i);
if (i % 2 == 0)
divTwo(i);
if (d[i - 1] + 1 < d[i]) {
d[i] = d[i - 1] + 1;
path[i] = i - 1;
}
}
sb.append(d[N] + "\n");
while (N > 0) {
sb.append(N + " ");
N = path[N];
}
System.out.println(sb);
br.close();
}
private static void divThree(int i) {
if (d[i / 3] + 1 < d[i]) {
d[i] = d[i / 3] + 1;
path[i] = i / 3;
}
}
private static void divTwo(int i) {
if (d[i / 2] + 1 < d[i]) {
d[i] = d[i / 2] + 1;
path[i] = i / 2;
}
}
}복잡도
- 시간: O(N) — N까지 한 번 순회하며 각 상태를 O(1)에 처리
- 공간: O(N) — DP 배열 및 경로 배열