[백준] 9095번 1, 2, 3 더하기 JAVA

DP문제 중에서도 쉬운편에 속하는 문제인것같다. 

정답 비율이 62%나 되는 걸 보니?ㅋㅋ

 

정수 n이 주어졌을 때, n을 1, 2, 3의 합으로 나타내는 방법의 수를 구하는 문제이다.

 

결론적으로 점화식은

arr[n] = arr[n-3] + arr[n-2] + arr[n-1] 이 된다.

 

예를 들어 n이 10이라고 했을 때 1, 2, 3의 합으로 10이 될 수 있는 수는

10-1, 10-2, 10-3인 9, 8, 7 이기 때문에 이들의 경우의 수를 합치면 10의 방법의 수가 나온다.

 

import java.io.*;

public class Main {
    public static void main(String args[]) throws IOException {
        BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
//        n은 양수이며 11보다 작다.
        int[] caseArr = new int[11];
        int cnt = Integer.parseInt(reader.readLine().toString());
        caseArr[1] = 1;
        caseArr[2] = 2;
        caseArr[3] = 4;

        for(int i=4; i< caseArr.length; i++){
            caseArr[i] = caseArr[i-3] + caseArr[i-2] + caseArr[i-1];
        }
        while(cnt > 0) {
            int testCase = Integer.parseInt(reader.readLine().toString());
            System.out.println(caseArr[testCase]);
            cnt--;
        }
        reader.close();
    }
}

 

테스트 케이스의 범위가 좁아서 아예 처음부터 배열을 다 계산 해놓고

입력받아서 테스트 케이스 배열에 값을 뽑아줬다.

 

처음에는 막막햇는데 공부할수록 문제가 풀리니까 재미있게 느껴진다.

행복하다~~~