[Java] 백준(실버-3) 9095번 - 1,2,3 더하기

문제 풀이

---

이 문제는 DP를 활용해 점화식을 세워서 풀 수 있는 문제이다.

아이디어 도출

이 문제에서는 1, 2, 3의 합을 이용해 N을 구하는 경우의 수를 구해야 하기 때문에, 먼저 1, 2, 3을 만들 수 있는 경우의 수를 구해야 한다.

1 = {1} => 1개
2 = {1+1, 2} => 2개
3 = {1+1+1, 1+2, 2+1, 3} => 4개
4 = ?

위와 같이 1,2,3일 때의 경우의 수는 1개, 2개, 4개인 것을 알 수 있다. 그러면 N=4일 경우는 어떻게 구할까?

4 = (1+3) + (2+2) + (3+1)

잘 살펴보면 위처럼 1, 2, 3의 각 경우의 수에 +1, +2, +3을 해주면 4일 때의 경우의 수를 구할 수 있다. 결국 1, 2, 3일 때의 경우의 수는 알고 있기 때문에 이를 이용하여 N이 4일 때나 5일 때의 경우의 수를 구할 수 있게 된다.

5 = (1+4) + (2+3) + (3+2)

하나의 예를 추가로 들어 N=5일 경우도 1, 2, 3의 경우의 수에 +4, +3, +2를 해주면 구할 수 있는 것으로 보아 이제는 점화식을 구할 수 있다.

점화식
D[n] = D[n-3] + D[n-2] + D[n-1]

마지막으로, 이 점화식을 이용해 N일 때마다의 경우의 수를 테스트케이스마다 출력하면 된다.

문제 풀이를 위해 작성한 코드는 아래와 같다.

작성코드

---

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

class Main {    

    static int[] D = new int[11];

    public static void main(String[] args) throws IOException {
        
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        
        int T = Integer.parseInt(br.readLine());

        // 1,2,3일 때, 경우의 수를 기록
        D[0] = 0;
        D[1] = 1;
        D[2] = 2;
        D[3] = 4;

        /**
         * DP 점화식
         * D[i] = D[i-3] + D[i-2] + D[i-1]
         * N의 범위가 11까지기에 4부터 11까지의 경우의 수를 구한다.
         */
        for(int i=4; i<11; i++) {
            D[i] = D[i-3] + D[i-2] + D[i-1];
        }

        for(int i=0; i<T; i++) {
            int N = Integer.parseInt(br.readLine());
            bw.write(D[N]+"\n");
        }
        
        bw.close();
        br.close();
    }

}

출처

---

• 해당 문제의 저작권은 문제를 만든이에게 있으며 자세한 내용은 문제 링크에서 참조바랍니다.