백준 - 1463번 1로 만들기 <실버 3> - 자바 DP

 

쉬워 보였는디

 

처음엔 간단하게 생각했다.

초기값을 정하고, 연산 경우의 수를 따져서 간단하게 로직을 작성했었다.

가능한 큰 수인 3으로 나누는 경우가 좋을 것이라 판단했고, -1의 경우도 있기에 X % 3 == 1이면 2의 배수여도 먼저 -1 후 3을 나누는게 나을 거라고 판단했었다.

 

X가 10이라면

10 -> 5 -> 4 -> 2-> 1

10 -> 9 -> 3 -> 1

이런 차이도 있기 때문에 저런 로직을 추가했었다.

 

import java.util.*;
 
public class Main {
    public static void main(String[] args){
        //input
        Scanner sc = new Scanner(System.in);
        int X = sc.nextInt();
        int answer = 0;
 
 
        //logic
        while(true) {
            if(X == 1) {
                break;
            }else if(X % 3 == 1) {
                X -= 1;
            }else if (X % 3 == 0) {
                X /= 3;
            }else if (X % 2 == 0) {
                X /= 2;
            }else X -= 1;
        answer ++;
        }
        
        //output
        System.out.printf("%d",answer);
    }
}
 

<기존 코드>

 

가볍게 틀려주면서 반례를 고민해 봤는데

700 -> 699 -> 233 -> 232 -> 231 -> 77 -> 76 -> 75 -> 25 -> 24 -> 8 -> 4 -> 3 -> 1 

700 -> 350 -> 175 -> 174 -> 58 -> 29 -> 28 -> 14 -> 7 -> 6 -> 2 -> 1    

 

당연히 이런 반례들이 나타났다.

그럼 Math.min를 사용해서  가장 적은 경우의 수를 찾아보려 했고, DP를 이용하려 했다

6으로 나눠지는 경우도 결국 2,3으로 나누는 경우와 1을 뺀 경우를 비교하는 것과 같기 때문에 배제했다. 

 

dp [] 배열을 초기화하고, X가 1,2,3일 때 각각 0,1,1을 초기값으로 주었다.

이후 반복문을 진행하면서, dp[i -1] +1 로 값을 정해주고(이전 값에서 -1하면 한번 더 연산되기 때문에),

2로 나눠지거나 3으로 나눠지면 i/2 +1또는 i/3 +1와 비교해서 더 작은 값을 dp[i]에 넣어 주면

dp[]에는 X 이하의 모든 수가 배열에 정리가 된다.

 

ex) dp[10] 이라면

 

dp [4] = 2, Math.min( 2 , dp[2] +1 ) -> 2

dp[1]	dp[2]	dp[3]	dp[4]	dp[5]	dp[6]	dp[7]	dp[8]	dp[9]	dp[10]
0	1	1	2

dp [5] = 3

dp[1]	dp[2]	dp[3]	dp[4]	dp[5]	dp[6]	dp[7]	dp[8]	dp[9]	dp[10]
0	1	1	2	3

dp [6] = 4, Math.min( 4 , dp[3] +1 ) -> 2

dp [6] = 4, Math.min( 4 , dp[2] +1 ) -> 2

 

dp[1]	dp[2]	dp[3]	dp[4]	dp[5]	dp[6]	dp[7]	dp[8]	dp[9]	dp[10]
0	1	1	2	3	2

dp [7] = 3,

dp[1]	dp[2]	dp[3]	dp[4]	dp[5]	dp[6]	dp[7]	dp[8]	dp[9]	dp[10]
0	1	1	2	3	2	3

dp [8] = 4, Math.min( 4 , dp[4] +1 ) -> 3

dp[1]	dp[2]	dp[3]	dp[4]	dp[5]	dp[6]	dp[7]	dp[8]	dp[9]	dp[10]
0	1	1	2	3	2	3	3

dp [9] = 4, Math.min( 4 , dp[3] +1 ) -> 2

dp[1]	dp[2]	dp[3]	dp[4]	dp[5]	dp[6]	dp[7]	dp[8]	dp[9]	dp[10]
0	1	1	2	3	2	3	3	2

dp [10] = 3, Math.min( 3 , dp[5] +1 ) -> 3

dp[1]	dp[2]	dp[3]	dp[4]	dp[5]	dp[6]	dp[7]	dp[8]	dp[9]	dp[10]
0	1	1	2	3	2	3	3	2	3

 

 

import java.util.*;
 
public class Main {
    public static void main(String[] args){
        //input
        Scanner sc = new Scanner(System.in);
        int X = sc.nextInt();
        int []dp = new int[X+1]; // dp[]는 X를 1로 만드는 최소한의 수 배열
        dp[1] = 0; // 초기값 설정.
        dp[2] = 1;
        dp[3] = 1;
 
        //logic
        for(int i=4; i<= X; i++) { 
            dp[i] = dp[i-1] + 1; // 이전보다 + 1
            if(i % 2 == 0){        // 2로 나누어 진다면.
                dp[i] = Math.min(dp[i], dp[i/2] + 1); // i/2 +1과 비교해서 대입.
            }
            if(i % 3 == 0) {     // 3으로 나누어 진다면
                dp[i] = Math.min(dp[i], dp[i/3] + 1); // i/3 +1과 비교해서 대입.
            }
        }
        //output
        System.out.print(dp[X]);
    }
}
 

 

간단한데 이상하게 오래 걸린 문제였다,, 완전탐색 방식이 어색하기도 했고, '다른방법이 있겠지~' 싶어서 재귀도 써보고 수학적으로 다른게 있나..? 해서 규칙 찾다가 더 오래걸린 문제였다.

 

** 수정 - 이클립스에선 잘 작동했는데

이게 뭐람 했는데 1보다 작으면 배열 초기화에 있어서 오류가 발생했다.

X 조건을 추가~, 또는 초기값이 0이므로 그냥 없어도 무방했다.

 

import java.util.*;
 
public class Main {
    public static void main(String[] args){
        //input
        Scanner sc = new Scanner(System.in);
        int X = sc.nextInt();
        int []dp = new int[X+1]; // dp[]는 X를 1로 만드는 최소한의 수 배열
        
        if(X > 1) { // X가 1보다는 커야 배열이 성립.
            dp[0] = 0;
            dp[1] = 0;
            dp[2] = 1;
            dp[3] = 1;
        }
        //logic
        for(int i=2; i<= X; i++) { 
            dp[i] = dp[i-1] + 1; // 이전보다 + 1
            if(i % 2 == 0){        // 2로 나누어 진다면.
                dp[i] = Math.min(dp[i], dp[i/2] + 1); // i/2 +1과 비교해서 대입.
            }
            if(i % 3 == 0) {     // 3으로 나누어 진다면
                dp[i] = Math.min(dp[i], dp[i/3] + 1); // i/3 +1과 비교해서 대입.
            }
        }
        //output
        System.out.print(dp[X]);
    }
}