[JAVA] 백준 9095번

9095번 - 1, 2, 3 더하기

 

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;

public class Main {

	static int[] dp;

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

		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

		dp = new int[12];

		int T = Integer.parseInt(br.readLine());

		dp[1] = 1;
		dp[2] = 2;
		dp[3] = 4;

		for (int i = 4; i <= 11; i++) {

			dp[i] = dp[i - 3] + dp[i - 2] + dp[i - 1];
		}

		for (int loop = 0; loop < T; loop++) {
			int N = Integer.parseInt(br.readLine());
			bw.write(String.valueOf(dp[N]));
			bw.newLine();
		}

		bw.flush();
		bw.close();

	}

}

 

정답을 맞춘 풀이방법

1. 일반적인 DP문제로 규칙을 찾으면 쉽게 풀 수 있는 문제

2. N >= 3 일 때 dp[n] = dp[n-3] + dp[n-2] + dp[n-1] 임

3. N이 최대 11까지 밖에 안되므로 dp값을 전부 구한 후 반복되는 T의 개수만큼 출력함