자바로 백준 9095 풀기

• 실버 3단계 문제

풀이)

11보다 작은 자연수 N에 대하여, 1, 2, 3의 합으로 나타낼 수 있는 가짓수를 구하여라. 단, 1+2와 2+1은 다른 것으로 치부한다.

다이나믹 프로그래밍 방식으로 풀어야 한다.
DP란 일반적인 재귀에서 더 나아가, 이전 재귀 계산 값을 저장하고 그 다음 재귀에서 계산 값을 활용하는 방식이다.

• DP 방식으로 풀기 위해선 동일한 문제가 반복돼서 나타나는 경우, 부분 문제의 해답이 전체 문제의 해답으로 확장될 수 있는 경우여야 한다.

해당 문제는 'N=4일 때' = 'N=3일 때'+'N=2일 때'+'N=1일 때' 이므로 DP를 이용해 해결한다.

내 코드)

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

public class Backjoon9095 {

	
	public static void main(String[]args) throws IOException{
		BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
		int T = Integer.parseInt(bf.readLine());
		StringBuilder sb = new StringBuilder();
		
		int[] dp = new int[11];
		dp[1] = 1;
		dp[2] = 2;
		dp[3] = 4;
				
		for(int i=4;i<=10;i++) {
			dp[i] = dp[i-1] + + dp[i - 2] + dp[i - 3];
		}
		
		for(int t=0;t<T;t++) {
			int N = Integer.parseInt(bf.readLine());
			sb.append(dp[N]);
			sb.append("\n");
		}
		System.out.println(sb);
	}
}