[오늘의 코테 연습장] - 백준 9095번

문제

문제 해결과정

숫자	1,2,3으로 만들수 있는 방법	1,2,3으로 만들 수 있는 가짓수
1	1	1
2	1+1 /2	2
3	1+1+1/2+1/1+2/3	4
4	1+1+1+1/2+1+1/1+2+1/3+1/1+3/1+1+2/2+2	7
5	1+1+1+1/2+1+1/1+2+1/3+1/1+3/1+1+2/2+2	13

여기서 더 작은 문제로 쪼개보면 중복되는 문제들이 존재한다.

1,2,3으로 만들 수 있는 숫자의 방법을 n{ ] 으로 두면

5을 예로 들면

n[5] →n4 + n3 +n2 이 된다.

n[5]=n[4]+n[3] + n[2] = 13 이 성립한다.

코드

import java.util.Scanner;

 public class Main {
     public static void main(String[] args) {
         Scanner scan = new Scanner(System.in);
         int T = scan.nextInt(); // 테스트 갯수 입력받기
         int[] n = new int[11];
         int N;
         for (int j = 1; j <= T; j++) {
              N=scan.nextInt();
             n[0] = 1;
             n[1] = 1;                                   ;
             n[2] = 2;
             for (int i = 3; i <= N; i++) {
               n[i] = n[i-1] + n[i-2] + n[i - 3];

             }
             System.out.println(n[N]);

         }
     }

 }