[백준 9095] 1,2,3 더하기 - 자바

 

조건

 

1. 합을 나타낼땐 수를 1개 이상 사용

2. 첫번째 줄에 테스트 케이스의 갯수가 주어지고, 정수 n이 주어짐

3. n은 11미만의 양수

 

arr[n]이 방법의 수라고 생각하면

 

arr[1]=1   n=1일 때 (1)   

arr[2]=2   n=2일 때 (1,1) (2)

arr[3]=4   n=3일 때 (1,1,1) (1,2) (2,1) (3)

arr[4]=7   n=4일 때 (1,1,1,1) (1,1,2) (1,2,1) (2,1,1) (1,3) (3,1) (2,2)

arr[5]=?    n=5일 때. 1+4 / 2+3 / 3+2 로 나눠서 생각할 수 있다.

          = arr[4]+arr[3]+arr[2]=13

 

이런식으로 arr의 값을 구할 수 있으니

arr[n]=arr[n-1]+arr[n-2]+arr[n-3]이라는 공식을 도출할 수 있다.

 

전체 코드

import java.io.*;
 
public class Main {
    public static void main(String[] args) throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        
        int T=Integer.parseInt(br.readLine());
        int[] arr=new int[11];
 
        arr[0]=0;
        arr[1]=1;
        arr[2]=2;
        arr[3]=4;
  
        for(int i=0;i<T;i++){
            int num=Integer.parseInt(br.readLine());
            for(int a=4;a<=num;a++){
                arr[a]=arr[a-1]+arr[a-2]+arr[a-3];
            }
            System.out.println(arr[num]);
        }
        
    }    
}