👨‍💻 문제

---

✍️ 풀이

🏹 점화식

해당 문제는 (1, 2)와 (2, 1)을 같은 조합으로 생각한다.

for (...) {
	arr[i] += arr[i-1] + arr[i-2] + arr[i-3];
}

그렇기에 단순히 위와 같은 점화식을 작성하게 되면,

i	0	1	2	3
0	( )
1	( )	(1)
2	( )	(1)	(1, 1), (2)
3	( )	(1)	(1, 1), (2)	(1, 2), (1, 1, 1), (2, 1), (3)

(1, 2)와 (2, 1)을 다른 조합으로 생각하기 때문에 다른 방식을 사용한다.

바로 1 ~ 3의 수를 한 번에 더하지 않고,
각각의 수를 한 바퀴씩 반복문을 돌리는 것이다.

for (...) {
	arr[i] += arr[i - 1];
}
for (...) {
	arr[i] += arr[i - 2];
}
for (...) {
	arr[i] += arr[i - 3];
}

i	0	1	2	3
0	( )
1	( )	(1)
2	( )	(1)	(1, 1)
3	( )	(1)	(1, 1)	(1, 1, 1)

i	0	1	2	3
0	( )
1	( )	(1)
2	( )	(1)	(1, 1), (2)
3	( )	(1)	(1, 1), (2)	(1, 1, 1), (1, 2)

i	0	1	2	3
0	( )
1	( )	(1)
2	( )	(1)	(1, 1), (2)
3	( )	(1)	(1, 1), (2)	(1, 1, 1), (1, 2), (3)

위와 같이 순서가 다른 같은 조합을 만들지 않게 된다.

---

📄 전체 소스코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

public class Main {

    private static final int N = 10000;

    public static void main(String[] args) throws IOException {

        long[] arr = new long[N + 1];
        arr[0] = 1;

        for (int add=1; add<=3; add++) {
            for (int i=1; i<=N; i++) {
                if (i - add >= 0) {
                    arr[i] += arr[i - add];
                }
            }
        }

        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringBuilder sb = new StringBuilder();
        int T = Integer.parseInt(br.readLine());

        for (int t=0; t<T; t++) {
            int n = Integer.parseInt(br.readLine());
            sb.append(arr[n]);
            sb.append('\n');
        }

        System.out.print(sb);

    }

}