[BOJ] 12852 1로 만들기 2 (Java)

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

 

<아이디어>

우선 N의 범위가 최대 백만이기에, 각 3가지 경우를 모두 메모이제이션 하는 것은 불가능했다.

그렇다면 최대 1차원 배열을 사용해야 한다는 것인데, 규칙이 뭘까? 하고 dp 배열을 그려봤다.

예제 2를 대입해서 배열의 값으로는 연산 횟수를 저장하고자 할 때,

이전 값에서 * 3, * 2, + 1 을 해서 현재 값이 되는 수의 배열 값 + 1(1회 연산) 을 한 것들 중 최솟값을 저장 하면 되겠다 싶었다.

그래서 처음에 아래와 같이 작성하여 제출했다.

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

public class Main {

    static class Point{
        int cnt;
        int idx;
        Point(int cnt, int idx){
            this.cnt = cnt;
            this.idx = idx;
        }
    }

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

        Point[] dp = new Point[n+1];
        // 초기화
        for(int i=0; i<n+1; i++){
            dp[i] = new Point(Integer.MAX_VALUE, 0);
        }
        dp[1] = new Point(0, 0);

        for(int i=2; i<n+1; i++){
        // 시간초과의 원인인 부분
            for(int j=1; j<i; j++){
                // 이전 값에서 현재 값으로 만들 수 있는 경우
                if(j * 3 == i || j * 2 == i || j + 1 == i) {
                    if(dp[i].cnt > dp[j].cnt+1){
                        dp[i] = new Point(dp[j].cnt+1, j);
                    }
                }
            }
        //
        }
        StringBuilder sb = new StringBuilder();
        sb.append(dp[n].cnt + " \n" + n);
        while(dp[n].idx > 0){
            sb.append(" " + dp[n].idx);
            n = dp[n].idx;
        }
        System.out.println(sb.toString());
    }
}

 

하지만 시간초과가 떴다..

이중 반복문을 써서 이전의 모든 값들을 다 확인해 보는 것이 불필요한 연산을 추가 시켰다.

따라서 이를 모든 값을 확인 하는 것이 아닌 3으로 나누어 떨어지는 이전 값, 2로 나누어 떨어지는 이전 값, 1을 뺀 이전 값

이렇게 3경우를 지정해서 각각의 경우를 계산한 최솟값을 저장할 수 있도록 하였다. (최대 n-1 번의 연산에서 3번으로)

그렇게 제출하여 통과한 코드는 아래와 같다!

 

참, 최솟값을 찾는 연산 과정에서 포함되는 수는 각각의 경우에 이전 값의 인덱스를 기억할 수 있게 함으로써 해결했다.

(즉, 마지막 값인 n 이 만들어지는 이전 값은 idx가 9이고, 9가 만들어지는 이전 값은 idx가 3이고 이런식으로!)

 

 

<제출코드>

package BOJ.DP;

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

public class BOJ_12852_1로만들기2 {

    static class Point{
        int cnt;
        int idx;
        Point(int cnt, int idx){
            this.cnt = cnt;
            this.idx = idx;
        }
    }

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

        Point[] dp = new Point[n+1];
        // 초기화
        for(int i=0; i<n+1; i++){
            dp[i] = new Point(Integer.MAX_VALUE, 0);
        }
        dp[1] = new Point(0, 0);

        for(int i=2; i<n+1; i++){
            // 1. 나누기 3
            if(i % 3 == 0) {
                if(dp[i].cnt > dp[i / 3].cnt+1){
                    dp[i] = new Point(dp[i / 3].cnt+1, i / 3);
                }
            }
            // 2. 나누기 2
            if(i % 2 == 0) {
                if(dp[i].cnt > dp[i / 2].cnt+1){
                    dp[i] = new Point(dp[i / 2].cnt+1, i / 2);
                }
            }
            // 3. 빼기 1
            if(dp[i].cnt > dp[i - 1].cnt+1){
                dp[i] = new Point(dp[i - 1].cnt+1, i - 1);
            }
        }

        StringBuilder sb = new StringBuilder();
        sb.append(dp[n].cnt + " \n" + n);
        while(dp[n].idx > 0){
            sb.append(" " + dp[n].idx);
            n = dp[n].idx;
        }
        System.out.println(sb.toString());
    }
}