[BOJ] 15988 1, 2, 3 더하기 3 (Week 7, No.12)

문제

정수 4를 1, 2, 3의 합으로 나타내는 방법은 총 7가지가 있다. 합을 나타낼 때는 수를 1개 이상 사용해야 한다.

1+1+1+1
1+1+2
1+2+1
2+1+1
2+2
1+3
3+1
정수 n이 주어졌을 때, n을 1, 2, 3의 합으로 나타내는 방법의 수를 구하는 프로그램을 작성하시오.

입력

첫째 줄에 테스트 케이스의 개수 T가 주어진다. 각 테스트 케이스는 한 줄로 이루어져 있고, 정수 n이 주어진다. n은 양수이며 1,000,000보다 작거나 같다.

출력

각 테스트 케이스마다, n을 1, 2, 3의 합으로 나타내는 방법의 수를 1,000,000,009로 나눈 나머지를 출력한다.

예제 입력 1

3
4
7
10

예제 출력 1

7
44
274

---

풀이

dp.

n=1 ~ 3 까지는 지정된 값으로 나오지만, 4 이상은 이전의 세 값을 더한 게 현재의 값이 된다.

4가 될 수 있는 경우 = 1이 될 수 있는 경우 + 2가 될 수 있는 경우 + 3이 될 수 있는 경우

나중에 큰 값이 되면 각 값을 더할 때 int의 범위를 넘길 수 있기 때문에 long으로 지정해줬다.

---

코드

배열 사용

import java.io.*;

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

        int t = Integer.parseInt(br.readLine());
        if (t == 0) return;
        
        int[] ns = new int[t];

        for (int i = 0; i < t; i++) {
            int n = Integer.parseInt(br.readLine());
            ns[i] = n;
        }

        for (int i = 0; i < t; i++) {
            int curNum = ns[i];
            
            // base case
            if (curNum == 1) {
                System.out.println(1);
                continue;
            } else if (curNum == 2) {
                System.out.println(2);
                continue;
            } else if (curNum == 3) {
                System.out.println(4);
                continue;
            }

            long[] arr = new long[curNum + 1];
            arr[0] = 0;
            arr[1] = 1;
            arr[2] = 2;
            arr[3] = 4;
            for (int j = 4; j <= curNum; j++) {
                arr[j] = (arr[j - 1] + arr[j - 2] + arr[j - 3]) % 1000000009;
            }
            System.out.println(arr[arr.length - 1]);
        }
    }
}

ArrayList 사용

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

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

        int t = Integer.parseInt(br.readLine());
        if (t == 0) return;

        int[] ns = new int[t];

        for (int i = 0; i < t; i++) {
            int n = Integer.parseInt(br.readLine());
            ns[i] = n;
        }

        ArrayList<Long> list = new ArrayList<>();
        int curIdx = 0;

        for (int i = 0; i < t; i++) {
            int curNum = ns[i];
            // base case
            if (curNum == 1) {
                System.out.println(1);
                continue;
            } else if (curNum == 2) {
                System.out.println(2);
                continue;
            } else if (curNum == 3) {
                System.out.println(4);
                continue;
            }

            if (curIdx == 0) {
                list.add((long) 0);
                list.add((long) 1);
                list.add((long) 2);
                list.add((long) 4);
                curIdx = 4;

                for (int j = curIdx; j <= curNum; j++) {
                    list.add((list.get(j - 1) + list.get(j - 2) + list.get(j - 3)) % 1000000009);
                    curIdx++;
                }
            } else if (curNum < curIdx) {
                System.out.println(list.get(curNum));
                continue;
            } else {
                for (int j = curIdx; j <= curNum; j++) {
                    list.add((list.get(j - 1) + list.get(j - 2) + list.get(j - 3)) % 1000000009);
                    curIdx++;
                }
            }
            System.out.println(list.get(curNum));
        }
    }
}