12825번: 1로 만들기 2 - Kotlin, Java

12852번: 1로 만들기 2

사진: Unsplash의Antoine Dautry

 

 

문제

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

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

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

입력

첫째 줄에 1보다 크거나 같고, 106보다 작거나 같은 자연수 N이 주어진다.

출력

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

둘째 줄에는 N을 1로 만드는 방법에 포함되어 있는 수를 공백으로 구분해서 순서대로 출력한다. 정답이 여러 가지인 경우에는 아무거나 출력한다.

---

 

 

나의 풀이

이 문제는 DP를 사용하는 문제입니다. 문제 자체는 조건이 다 주어져 있기에 DP를 알고있다면 어렵지 않습니다. 다만 저는 처음에 주어진 연산 중 하나만 사용해야 하는 줄 알았어서, 좀 헤맸던것 같습니다.

저는 초기값을 dp[3]까지 넣어주었기 때문에 n이 1일때와 2일때는 if문을 통해 결과를 바로 출력해 주도록 했습니다.

 

dp는 index로 초기화 하였고, 경로를 route라는 배열을 따로 둬서 1이 되는 최솟값일 때에는 이전의 경로를 넣어주도록 했습니다. 경로는 index - 1로 초기화 하였습니다.

 

나머지는 3으로 나눠질 때, 2로 나눠질 때, -1할 때를 나눠서 초기화된 값과 비교하였습니다.

 

마지막 경로 출력은 dp[n]일 경우 dp[n]이 최소가 될 수 있었던 이전 경로가 route에 들어있기 때문에 이를 방문하고 기록하는 식으로 진행하였습니다.

 

Kotlin

fun main() = with(System.`in`.bufferedReader()) {

    val n = readLine().toInt()

    if (n == 1) {
        println(0)
        println(1)
        return@with
    }

    if (n == 2) {
        println(1)
        println("2 1")
        return@with
    }

    val dp = IntArray(n + 1).mapIndexed { index: Int, i: Int -> index }.toIntArray()
    val route = IntArray(n + 1).mapIndexed { index: Int, i: Int -> index - 1 }.toIntArray()

    dp[2] = 1
    route[2] = 1
    dp[3] = 1
    route[3] = 1

    for (i in 4..n) {
        if (i % 3 == 0) {
            if (dp[i / 3] + 1 <= dp[i]) {
                dp[i] = dp[i / 3] + 1
                route[i] = i / 3
            }
        }

        if (i % 2 == 0) {
            if (dp[i / 2] + 1 <= dp[i]) {
                dp[i] = dp[i / 2] + 1
                route[i] = i / 2
            }
        }

        if (dp[i - 1] + 1 < dp[i]) {
            dp[i] = dp[i - 1] + 1
            route[i] = i - 1
        }
    }

    val result = mutableListOf<Int>().apply { add(n) }

    var temp = route[n]
    while (true) {
        if (temp == 1) break

        result.add(temp)
        temp = route[temp]
    }
    result.add(1)

    println(dp[n])
    println(result.joinToString(" "))
}

 

 Java

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

public class Main {

    public static void main(String[] args) throws IOException {
        BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));

        int n = Integer.parseInt(bf.readLine());

        if (n == 1) {
            System.out.println(0);
            System.out.println(1);
            return;
        }

        if (n == 2) {
            System.out.println(1);
            System.out.println("2 1");
            return;
        }

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

        for (int i = 0; i <= n; i++) {
            dp[i] = i;
            route[i] = i - 1;
        }

        dp[2] = 1;
        route[2] = 1;
        dp[3] = 1;
        route[3] = 1;

        for (int i = 4; i <= n; i++) {
            if (i % 3 == 0) {
                if (dp[i / 3] + 1 <= dp[i]) {
                    dp[i] = dp[i / 3] + 1;
                    route[i] = i / 3;
                }
            }

            if (i % 2 == 0) {
                if (dp[i / 2] + 1 <= dp[i]) {
                    dp[i] = dp[i / 2] + 1;
                    route[i] = i / 2;
                }
            }

            if (dp[i - 1] + 1 < dp[i]) {
                dp[i] = dp[i - 1] + 1;
                route[i] = i - 1;
            }
        }

        List<Integer> answer = new ArrayList<>();
        answer.add(n);

        int temp = route[n];
        while (temp != 1) {
            answer.add(temp);
            temp = route[temp];
        }
        answer.add(1);

        System.out.println(dp[n]);
        System.out.println(answer.toString().replace("[", "").replace("]", "").replace(",", ""));
    }
}