12852번: 1로 만들기 2

문제

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

1. X가 3으로 나누어 떨어지면, 3으로 나눕니다.
2. X가 2로 나누어 떨어지면, 2로 나눕니다.
3. 1을 뺍니다.

정수 N이 주어졌을 때, 위와 같은 연산 세 개를 적절히 사용해서 1을 만들려고 합니다. 연산을 사용하는 횟수의 최솟값을 출력하고, 그 최적의 과정에 포함되어 있는 수들을 출력하는 프로그램을 작성하는 문제입니다.

• 입력: 첫째 줄에 1보다 크거나 같고, 10^6보다 작거나 같은 정수 N이 주어집니다.
• 출력: 첫째 줄에 연산을 하는 횟수의 최솟값을 출력합니다. 둘째 줄에는 N을 1로 만드는 방법에 포함되어 있는 수를 공백으로 구분해서 순서대로 출력합니다. (정답이 여러 가지인 경우에는 아무거나 출력합니다.)

링크: https://www.acmicpc.net/problem/12852

풀이: 1차원 배열 DP와 이전 경로 기록(pre)

기존의 '1로 만들기' 문제에서 최소 연산 횟수를 구하는 d 배열에 추가로, 역추적을 위한 pre 배열을 도입하여 해결하는 방식입니다.

• 상태 및 경로 배열 정의:
  • d[i]: 숫자 i를 1로 만드는 데 필요한 최소 연산 횟수
  • pre[i]: 숫자 i가 1이 되는 최적의 경로 상에서, i 바로 다음에 와야 할 숫자 (즉, 연산을 한 번 수행한 직후의 숫자)
• 상태 전이 (Bottom-Up):
  • 숫자 2부터 N까지 순차적으로 반복문을 돕니다.
  • 1을 빼는 경우 (기본값): 모든 숫자는 1을 뺄 수 있으므로, 우선 d[i] = d[i - 1] + 1로 설정하고 이전 숫자를 pre[i] = i - 1로 기록합니다.
  • 2로 나누어 떨어지는 경우: 만약 i가 2의 배수이고, 2로 나누었을 때의 연산 횟수(d[i / 2] + 1)가 현재까지 기록된 횟수(d[i])보다 작다면, 값을 갱신하고 경로도 pre[i] = i / 2로 바꿉니다.
  • 3으로 나누어 떨어지는 경우: 마찬가지로 3의 배수인지 검사하고 더 유리하다면 최솟값과 경로를 갱신합니다.
• 역추적 출력:
  • 모든 계산이 끝난 후 d[n]을 통해 최솟값을 출력합니다.
  • for문을 이용하여 n부터 시작해 pre[i]를 타고 계속해서 이전 숫자로 이동하며 출력합니다.
  • 자바 배열의 기본 초기화 값인 0을 영리하게 활용하여, pre[1]의 값인 0에 도달할 때(i != 0) 반복문을 자연스럽게 종료합니다.

코드

import java.io.*;
import java.util.*;

public class Main {
    public static void main(String[] args) throws IOException {
       BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
       BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

       int n = Integer.parseInt(br.readLine());
       
       // d: 최소 연산 횟수 저장, pre: 최적 경로 역추적
       int[] d = new int[n + 1];
       int[] pre = new int[n + 1];

       d[1] = 0; // 1은 이미 1이므로 연산 횟수 0
       
       // Bottom-Up 방식의 DP 탐색
       for (int i = 2; i <= n; i++) {
          // 1. 1을 빼는 연산
          d[i] = d[i - 1] + 1;
          pre[i] = i - 1;
          
          // 2. 2로 나누는 연산 비교
          if (i % 2 == 0 && d[i] > d[i / 2] + 1) {
             d[i] = d[i / 2] + 1;
             pre[i] = i / 2;
          }
          
          // 3. 3으로 나누는 연산 비교
          if (i % 3 == 0 && d[i] > d[i / 3] + 1) {
             d[i] = d[i / 3] + 1;
             pre[i] = i / 3;
          }
       }

       // 최솟값 출력
       bw.write(d[n] + "\n");
       
       // 역추적 배열을 활용하여 경로 출력
       for (int i = n; i != 0; i = pre[i]) {
          bw.write(i + " ");
       }
       bw.flush();
    }
}

알고리즘 분류

다이나믹 프로그래밍 (Dynamic Programming), 그래프 탐색 (Graph Traversal), 역추적 (Backtracking)