알고리즘 풀이/백준

[백준][Java] 9095번 1, 2, 3 더하기

배게 2018. 5. 16. 20:42
728x90

시간 오지게 들여도 점화식을 제대로 못 찾았습니다.


점화식 문제들은 각 문제마다 전부 돌파구가


전혀 다르기 때문에 실수로 잘못된 방식으로 파면


시간낭비 어마어마하게 하고 잘 찾으면 3분컷도 가능한 것


같습니다.


dp[N] = dp[N-1] + dp[N-2] + dp[N-3]


N의 구성 성분을 구하기 위해 N-1, N-2, N-3에 각각 1,2,3,을 더해준다는


개념을 어떻게 접근해야 생각해내는지 의문입니다.


점화식 문제 0승 all패


 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
import java.util.Scanner;

public class Main {
	
	public static void main(String[] args) {
		
		Scanner sc = new Scanner (System.in);
		
		int T = sc.nextInt();
		
		for(int i=0; i<T; i++) {
			int input = sc.nextInt();
			int[] dp = new int[11];
			dp[1]=1;dp[2]=2;dp[3]=4;
			for(int j=4; j<=input;j++) {
				dp[j]=dp[j-1]+dp[j-2]+dp[j-3];
			}
			System.out.println(dp[input]);
		}
		
	}
}