[BAEKJOON] 9095번 : 1, 2, 3 더하기

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

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());
		
		// 테스트 케이스 배열
		int[] arr = new int[T];
		int max = 0;
		for(int i=0;i<T;i++) {
			arr[i] = Integer.parseInt(br.readLine());
			if(max<arr[i]) {
				max = arr[i];
			}
		}
		
		// 문제의 조건 : n은 양수고 11보다 작음
		int[] d = new int[11];

		d[1] = 1;
		d[2] = 2;
		d[3] = 4;
		
		// 점화식 : d[i] = d[i-1] + d[i-2] + d[i-3];
		for(int i=4; i<=max;i++) {
			d[i] = d[i-1] + d[i-2] + d[i-3];
		}
		
		// 각 테스트 케이스의 결과 출력
		for(int i=0; i<T;i++) {
			System.out.println(d[arr[i]]);
		}
	}

}

 

이번 문제는 '점화식을 잘 이끌어 낼 수 있느냐' 가 요점이라고 생각합니다.

(다이나믹 프로그래밍 기법을 이용)

 

 

소스 설명은 주석을 참고해주세요.

 

좋은 지적과 지식 공유는 언제나 환영합니다^^