백준_9095 1, 2, 3 더하기(자바) / DP

시간&메모리 제한

 

문제

 

입력&출력

 

문제풀이

package com.back;

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

public class Back_9095 {

	public static void main(String[] args) throws NumberFormatException, IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		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];
		}
		
		int testCase = Integer.parseInt(br.readLine());
		StringBuilder sb = new StringBuilder();
		for (int tc = 0; tc < testCase; tc++) {
			int N = Integer.parseInt(br.readLine());
			sb.append(dp[N]+"\n");
		}
		System.out.println(sb);
	}
}

 

※ 내 생각

이 문제는 DP를 이용해서 푸는 문제입니다.
1,2,3 의 수가 주어졌기 때문에
1을 만드는 경우
2를 만드는 경우
3을 만드는 경우
의 각각의 경우를 구해줍니다.

4를 만드는 경우
1을 만들었던 경우 + 3을
2를 만들었던 경우 + 2를
3을 만들었던 경우 + 1을
하면  4를 만들수 있기 때문에 이전에 만들었던 3개의 경우를 던해주면 해결이 됩니다.