[java] 백준 알고리즘 9095번 1,2,3 더하기 풀이 소스

계산하다보니 입력한 케이스에 대해 입력한 케이스의 3가지 케이스의 경우의 수를 다 더하니

현재 입력한 케이스의 경우의 수가 나왔다. (귀납법적인 결론 도출..)

그래서 생각해보니 현재 케이스의 바로 직전(-1)의 케이스의 경우는 '1'을 더해주기 전의 총 케이스를 구한 값과 같다.

그리고 2번째 전의 케이스(-2)의 경우 '2'를 더 해주기전의 총 케이스를 구한 값과 같다.

3번째 전의 케이스(-3)의 경우 '3'을 더 해주기전의 총 케이스를 구한 값과 같다. 

* 1이 왔을 때 n의 케이스 = 1 + (n-1)의 값을 구하기 위한 총 케이스

* 2가 왔을 때 n의 케이스 = 2 + (n-2)의 값을 구하기 위한 총 케이스

* 3이 왔을 때 n의 케이스 = 3 + (n-3)의 값을 구하기 위한 총 케이스

이란 결과가 나온다.

예를 들어, 5를 입력한다면,

* 1 +가 되었을 때 5의 케이스 = 1 + 4의 총 케이스

* 2 + 가 되었을 때 5의 케이스 = 2 + 3의 총 케이스

* 3+ 가 되었을 때 5의 케이스 = 3 +2의 총 케이스

5의 총 케이스는 4의 총 케이스 + 3의 총 케이스 + 2의 총 케이스이다. 

그럼 1이 오거나 2가 오거나 3이 오거나 했을 때 그 수를 제외한만큼의 총 경우의 수를 구할 수 있다.

코드는 아래와 같이 만들었다. 

- 참고로 동적으로 배열을 선언하니 런타임 에러가 계속 나서 미리 배열 초기 크기를 선언해주었다. 

import java.util.Scanner;
 
public class Baekjoon9095 {
 
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        
        int t = scanner.nextInt();
        int n;
        
        int[] output = new int[11]; //동적으로 생성시키니 메모리 초과가 되서 정적으로 선언
        output[1] = 1; // 1을 넣을 경우 경우의 수 1가지(1)
        output[2] = 2; // 2를 넣을 경우 경우의 수 2가지(1+1, 2)
        output[3] = 4; // 3을 넣을 경우 경우의 수 3가지 (1+1+1, 1+2, 2+1, 3)
        
        for(int i=0; i<t; i++){
            n = scanner.nextInt();
            
            for(int j=4; j<=n; j++){
                output[j] = output[j-1] + output[j-2] + output[j-3];
            }
            System.out.println(output[n]);
        }
        
 
    }
 
}