• 15988번 : 방법은 같지만, 9095는 최대 N이 10이므로 모두 구해도 시간상 문제는 없지만, 15988은 최대 N이 매우 크므로 max값을 확인하여 한정된 구간까지만 알고리즘을 수행해야 한다.

---

문제 풀이

우리가 정수 N을 1,2,3의 합으로만 표현하고 싶다.
이 중 나는 "마지막에 더해질 수" 또한 1,2,3 중 하나라는 것에 집중했따.
우리가 N을 만들 수 있는 방법은 3가지이다.

1. (N-1) + 1

2. (N-2) + 2

3. (N-3) + 3

N-1, N-2, N-3 또한 위와 같은 형식으로 구할 수 있을 것이다.

즉, 점화식은 아래와 같다
$DP(N) = DP(N-1) + DP(N-2) + DP(N-3)$

• DP(N) : N을 만들 수 있는 경우의 수

---

코드

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

public class Main {
	static StringBuilder sb = new StringBuilder();
	static int N;
	static int[] answer = new int[11];
	
	static void dp() {
		answer[0] = 1;
		answer[1] = 1;
		answer[2] = 2;
		for(int i=3;i<=10;i++) {
			answer[i] = answer[i-1]+answer[i-2]+answer[i-3];
		}
	}
	
	public static void main(String[] args) throws IOException {
		FastReader sc = new FastReader();
		
		int T = sc.nextInt();

		dp();

		for(int t = 0;t<T;t++) {
			int tmp = sc.nextInt();
			sb.append(answer[tmp]).append("\n");
		}
		System.out.println(sb);
	}
	
	static class FastReader // 빠른 입력을 위한 클래스
}

---

결과

• 2번째 줄 틀렸습니다 : 구하고 싶은 답 중 최댓값까지의 범위만 DP 배열을 채워 문제를 풀려고 했는데, 이 과정에서 Sorting을 사용해서 답의 순서가 맞지 않게 되었다.