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

https://www.acmicpc.net/problem/9095

9095번: 1, 2, 3 더하기

풀이

사용한 알고리즘: 다이나믹 프로그래밍

 

풀이전략

아래의 표는 n 입력에 따라 합으로 나타낼 수 있는 경우의 수들을 나타낸다.

빨간선을 기준으로 

첫번째 문단은 1 + [이전의 경우의수]

두번째 문단은 2 + [2번째 전의 경우의수]

세번째 문단은 3 + [3번째 전의 경우의수]

가 출력되는 것을 확인할 수 있다.

 

따라서 d[i]를 i 입력 시 합으로 나타낼 수 있는 수의 개수라고 할 때

d[i]=d[i-1]+d[i-2]+d[i-3]  라는 식이 도출된다.

 

제출코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

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 d[]=new int[11];
        d[1]=1;
        d[2]=2;
        d[3]=4;
        for(int i=4;i<11;++i){
            d[i]=d[i-1]+d[i-2]+d[i-3];
        }

        for(int t=0;t<T;++t){
            int n = Integer.parseInt(br.readLine());
            System.out.println(d[n]);
        }
    }
}