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

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

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

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

시간낭비 어마어마하게 하고 잘 찾으면 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]); } } }