링크

1, 2, 3 더하기

문제

풀이

1 -> 1
2 -> 1+1, 2
3 -> 1+1+1, 2+1, 1+2, 3
4 -> 1+1+1+1, 2+1+1, 1+2+1, 1+1+2, 2+2, 3+1, 1+3
...
하다보니 규칙이 dp[n] = dp[n-1] + dp[n-2] + dp[n-3]이라는 규칙을 찾아서 풀었다.

코드

import java.util.*;

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 n = sc.nextInt();
            int dp[] = new int[n+1];

            for(int j=0;j<dp.length;j++){
                if(j == 0) dp[0] = 1;
                else if(j == 1) dp[1] = 2;
                else if(j == 2) dp[2] = 4;
                else{
                    dp[j] = dp[j-1] + dp[j-2] + dp[j-3];
                }
            }

//            System.out.println(Arrays.toString(dp));
            System.out.println(dp[n-1]);
        }

    }
}