[Java] 백준 1463 1로 만들기

1463 1로 만들기 문제 링크

문제

#1

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

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());
        int co = calculate(N, 0);
        bw.write(co+"");

        bw.flush();
        bw.close();
    }
    static int calculate(int N, int count) {
        if(N<=1) {
            return count;
        }
        int co = Integer.MAX_VALUE;
        if(N%3==0) {
            N = N/3;
            co = Math.min(calculate(N, count+1), co);
            N = N*3;
        }
        if(N%2==0) {
            N = N/2;
            co = Math.min(calculate(N, count+1), co);
            N = N*2;
        }
        N--;
        co = Math.min(calculate(N, count+1), co);
        N++;

        return co;
    }
}

• 빽트래킹 문제인 줄 알았는데.. 아닌가..?

#2

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

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());
        int[] dp = new int[N+1];
        dp[1] = 0;
        for(int i=2; i<=N; i++) {
            dp[i] = dp[i-1] + 1;
            if(i%2==0) dp[i] = Math.min(dp[i/2]+1, dp[i]);
            if(i%3==0) dp[i] = Math.min(dp[i/3]+1, dp[i]);
        }
        bw.write(dp[N]+"");

        bw.flush();
        bw.close();
    }
}

• 아 좀만 더 생각하면 됐는데
• 이전 꺼의 조합을 생각해본답시고 9->7+2 이러고 있었네..
• 당연히 9->3*3 으로 생각을 해야지..