[자바] 1463번 1로 만들기. 2021-06-30

문제는 우선 처음 아이디어를 내고 DP[i] =num 이 무엇을 의미하는지와, N-1항에서 N항으로 어떻게 갈수 있는지를 파악하기만 하면 쉽게 풀린다.

 

두가지 풀이법이 있다.

첫번째는 내 풀이법인데 난 이것이 DP[i]의 정의를 더욱 더 직관적으로 이해할수 있는 코드라고 생각한다. 물론 시간초과나서 틀렸지만. 하지만 알고리즘 원리는 똑같으니 같은 해답이다.

 

나는 DP[i]=num 의 정의를 N부터 시작해서 연산을 통해 i를 만들수 있는 연산의 최솟값 num 으로 정의했고,

다른 좀더 빠른 방식으로는. i를 1로 만들수 있는 최소연산횟수 num으로 정의했다.

 

내가 한 방법이 조금 더 문제의 조건에 직관적이긴 하지만, 시간초과가 난게 아마 2중 for문으로 현재 인덱스보다 크고 N보다 작은 것중에 2나 3으로 나눌수 있으면 비교하는 과정에서 난 거 같다.

 

 

import java.util.Scanner;

public class Main {


    public static void main(String[] args) {
        Scanner s = new Scanner(System.in);

       int N=s.nextInt();
       int[] dp=new int[N+1];
       //dp[i]에 저장시킬 것의 정의 : 숫자 i를 만들수 있는 가장 작은 연산횟수.
       dp[N]=0;
       for(int i=N-1;i>=1;i--){
           dp[i]=dp[i+1]+1;
           //기본 디폴트로는 그전 dp인덱스(숫자)에서 -1 연산한 횟수를 더해준다.
           for(int j=i+1;j<=N;j++){
               if(j%3==0&&j/3==i){

                   dp[i]=Math.min(dp[j]+1,dp[i]);
               }
               else if(j%2==0&&j/2==i){

                   dp[i]=Math.min(dp[j]+1,dp[i]);
               }
           }
       }
        System.out.println(dp[1]);

    }
}

 

DP[i] =num 의 정의를 숫자 i를 만들수 있는 최소 연산횟수: num 이라고 두고 짠 코드.

 

import java.util.Scanner;

public class Main {


    public static void main(String[] args) {
        Scanner s = new Scanner(System.in);

       int N=s.nextInt();
       int[] dp=new int[N+1];
      dp[0]=0;
      dp[1]=0;
        for (int i = 2; i < dp.length; i++) {
            dp[i]=dp[i-1]+1;
            if(i%3==0){
                dp[i]=Math.min(dp[i/3]+1,dp[i]);
            }
            if(i%2==0){
                dp[i]=Math.min(dp[i/2]+1,dp[i]);
            }

        }
        System.out.println(dp[N]);

    }
}

DP[i]=num 을 숫자 i를 1로 만들기 위한 최소연산횟수: num 으로 두고 짠 코드.

 

공부시간 1시간

순공시간 30분