[Silver III] 1로 만들기 - 1463 (java)

문제 설명

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

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

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

입력

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

출력

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

 

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

public class Main {
    
    
    public static void main(String [] args)throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int num = Integer.parseInt(br.readLine());
        
        int [] arr = new int [num+1];
        
        
        if(num>1){
            arr[2] = 1;
        }
        if(num>2){
            arr[3] = 1;
        }
       

        for(int i=4; i<=num; i++){

            int cnt3 = Integer.MAX_VALUE;
            int cnt2 = Integer.MAX_VALUE;
            int cnt1 = Integer.MAX_VALUE;

            if(i %3 ==0){
                cnt3 = arr[i/3];
            }
            if(i %2 ==0){
                cnt2 = arr[i/2];
            }
            
            cnt1 = arr[i-1];
            

            int min = Math.min(cnt3,Math.min(cnt2,cnt1));
           
            arr[i] = min +1;
        }
        System.out.println(arr[num]);
    }
    
}

 

1. 3으로,2로 나눈다고하기때문에 

초기값 arr[3], arr[2]는 미리 설정해주기. 

 

2. 그 다음부터는 중복계산을 피하기위해 

계산했던 값 정렬에 저장하기

 

3. 저장할때 원리는 

3으로 나눈값, 2로 나눈값, -1 값 중에 

제일 작은 값을 가져와서 +1 해주기 (나눈값,뺀값까지 도달해야하는 연산1회) 

 

 

 

 

DP 기초 문제 풀어보기.

오... 나 스스로 메모제이션!을 생각해낸걸 기특하게 생각.. ㅋㅋㅋㅋ 

 

알고리즘 문제를 계속 회피하고있었는데 

이러다간 코테 풀지도 못하겠단 생각으로 

정면 돌파 시작 .. ... 

 

준비되어있는 사람이 기회가 왔을때 잡을 수 있다!

 

 

 

---

리팩토링 

import java.io.*;

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

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

        int[] dp = new int[num + 1];
        for (int i = 2; i <= num; i++) {
            dp[i] = dp[i - 1] + 1;
            if (i % 2 == 0) dp[i] = Math.min(dp[i], dp[i / 2] + 1);
            if (i % 3 == 0) dp[i] = Math.min(dp[i], dp[i / 3] + 1);
        }
        System.out.println(dp[num]);
    }
}

 

1. num ==1 일때 바로 return 

 

2. 2랑 3일 때 1로 자동처리 

dp[i] 를 갱신하면서 처리 (cnt3, cnt2, cnt1 변수 필요없음) 

 

 

 

위가 리팩토링 코드

아래가 처음 코드