[Java] 백준 1463번 : 1로 만들기 <Silver 3>

⚠️ 내맘대로 작성한 코드이기 때문에 비합리적 진행과 근거없는 추론이 있을 수 있습니다!⚠️

 

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

1463번: 1로 만들기

Code

---

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Arrays;


public class Main {
    BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));

    void run() throws IOException {
        ArrayList<Integer> arr = new ArrayList<>(Arrays.asList(0,1,1)); // 1,2,3 초기화
        int num = Integer.parseInt(bf.readLine());
        int find = 3, min = 0;
        while(true){
            if(num <= 3){
                System.out.println(arr.get(num-1));
                break;
            }

            find++;
            min = 999999999;

            if((find%3 == 0) && (arr.get(find/3 - 1) < min)){
                min = arr.get(find/3 - 1) + 1;
            }
            if((find%2 == 0) && (arr.get(find/2 - 1) < min)){
                min = arr.get(find/2 - 1) + 1;
            }
            if(arr.get(find-2) < min){
                min = arr.get(find - 2) + 1;
            }
            if(find == num){
                System.out.println(min);
                break;
            }
            arr.add(min);
        }
    }

    public static void main(String[] args) {
        Main my = new Main();
        try {
            my.run();
        }catch(Exception e){}
    }
}

---

Code 필수 요소

1. Dynamic Programming(동적 프로그래밍) 사용

2. 규칙 찾기

 

이것만 생각해내면 절반은 끝났다.

 

// Dynamic Programming(동적 프로그래밍) 사용

Dynamic Programming이란?

아래에 쓰여있다.

https://naemamdaelo.tistory.com/27

알고리즘 - Dynamic Programming(동적 계획법)

 

//규칙 찾기

1 : 0

2 : 1 

3 : 1

4 : 2

5 : 3

6 : 2

7 : 3

8 : 3

9 : 2

10 : 3 

이렇듯 4이상의 숫자의 경우 3으로 나누어 떨어지는것, 2로 나누어 떨어지는것, 1뺀것 세개를 비교해서 가장 작은 값에 +1 해주면 된다.

Ex) 6

6/3 = 2 : 1

6/2 = 3 : 1

6-1 = 5 : 3

=> 1+1 = 2

 

Ex)10

10/3 = 나누어 떨어지지 않음

10/2 = 5 : 3

10-1 = 9 : 2

=> 2+1 = 3

 

 

// 전체적 설명

규칙을 구한 후 해당 내용들을 ArrayList에 메모이제이션 하며 동적계획법을 바탕으로 문제를 해결한다.

 

동적 프로그래밍이 뭔지 공부하는데 상당히 좋은 문제 같다. 물론 난 바텀업을 사용했지만 탑다운도 가능할거다. 아마...?

 

 

-꿑-