[Java] 백준 9095번 : 1,2,3 더하기 <Silver 3>

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

 

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

9095번: 1, 2, 3 더하기

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 {
        int num = Integer.parseInt(bf.readLine());

        find(num);
    }

    void find(int n) throws IOException{
        for(int i = 0; i < n; i++) {
            ArrayList<Integer> arr = new ArrayList<>(Arrays.asList(1,2,4));
            int goal = Integer.parseInt(bf.readLine());
            int number = 3;
            while (true) {
                if (goal < 4) {
                    System.out.println(arr.get(goal - 1));
                    break;
                }
                number++;

                arr.add(arr.get(number - 2) + arr.get(number - 3) + arr.get(number - 4));
                if (number == goal) {
                    System.out.println(arr.get(number - 1));
                    break;
                }
            }
        }
    }

    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문제의 핵심은 이 문제가 Dynamic Programming을 사용해야 한다는 것을 깨닫는 것이다. 

 

// 규칙 찾기

X = (X-1) + (X-2) + (X-3)

 

// 전체적 설명

바텀업 방식을 사용하여 ArryList에 해당하는 값을 하나씩 저장하며 해당 값에 접근한다.

 

동적 계획법이란? 

https://naemamdaelo.tistory.com/27

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

 

 

 

-꿑-