9095

1. 1, 2, 3 더하기

정수 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의 합으로 나타내는 방법의 수를 구하는 프로그램을 작성하시오.

2. 나만의 문제 해결

F(n) = F(n-1) + F(n-2) + F(n-3)

여러 수를 입력받는다는 점을 주의!
List에 DP의 결과값들을 저장해서 불필요한 연산을 줄여주자
  

3. code

public class Main {
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		StringBuilder sb = new StringBuilder();
		int n = Integer.parseInt(st.nextToken());

		List<Integer> list = new ArrayList<>();
		list.add(1);
		list.add(2);
		list.add(4);
		int maxSize = 3;

		for (int i = 0; i < n; i++) {
			st = new StringTokenizer(br.readLine());
			int num = Integer.parseInt(st.nextToken());

			if (maxSize < num){
				for (int j = maxSize; j < num; j++) {
					list.add(list.get(j - 1) + list.get(j - 2) + list.get(j - 3));
				}
				maxSize = num;
			}
			sb.append(list.get(num - 1) +"\n");
		}

		System.out.println(sb);
	}
}