BOJ. Make into 1(2) (12852)

Approach

Let dp[x] be the minimum number of operations needed to reduce x to 1. The final operation from x must be one of subtracting one, dividing by two when divisible, or dividing by three when divisible. Therefore, for each x from 2 through N, compute dp[x] as one plus the minimum dp among those valid predecessors. Every predecessor is smaller than x, so its answer has already been computed.

Store the predecessor that produced the minimum alongside each dp[x]. Starting at N, repeatedly follow that predecessor until reaching 1; this reconstructs an optimal path in the required descending order. If multiple candidates have the same minimum, keeping any of them is valid and still yields an optimal path. For N = 1, dp[1] is zero and reconstruction prints just 1.

The invariant is that after processing x, dp[x] is the minimum operation count from x to 1, and its recorded predecessor is a valid next value on a path attaining that count. The recurrence checks every possible final operation, and all smaller states are already optimal, so it preserves this invariant. The dynamic-programming table and predecessor array each contain N + 1 entries; filling them and reconstructing the path take O(N) time overall and O(N) space.

Problem link

Java

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader input = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(input.readLine().trim());

        int[] dp = new int[n + 1];
        int[] predecessor = new int[n + 1];

        for (int value = 2; value <= n; value++) {
            int bestPrevious = value - 1;
            int bestSteps = dp[bestPrevious];

            if (value % 2 == 0 && dp[value / 2] < bestSteps) {
                bestPrevious = value / 2;
                bestSteps = dp[bestPrevious];
            }
            if (value % 3 == 0 && dp[value / 3] < bestSteps) {
                bestPrevious = value / 3;
                bestSteps = dp[bestPrevious];
            }

            dp[value] = bestSteps + 1;
            predecessor[value] = bestPrevious;
        }

        StringBuilder output = new StringBuilder();
        output.append(dp[n]).append('\n');
        for (int value = n; ; value = predecessor[value]) {
            output.append(value).append(' ');
            if (value == 1) {
                break;
            }
        }
        System.out.print(output);
    }
}