[BOJ] 9095 - 1, 2, 3 더하기 (Java)

알고리즘

• 다이나믹 프로그래밍

1. 문제

• N을 1,2,3의 합으로 나타낼 수 있는 경우의 수 구하기
  

2. Idea

• N-1번째 경우의 수에 1을 더하는 경우
• N-2번째 경우의 수에 2를 더하는 경우
• N-3번째 경우의 수에 3을 더하는 경우
• 순서가 존재하므로 가능

3. 풀이

3.1. 변수 선언 및 초기화

• int T: 테스트케이스 수
• int[] dp: 경우의 수를 저장할 배열

        BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
        int T=Integer.parseInt(br.readLine());
        int[] dp=new int[12];

3.2. dp 배열 초기화

        dp[0]=0;
        dp[1]=1;
        dp[2]=2;
        dp[3]=4;

3.3. dp 배열 각 인덱스 값 구하기

• 최대 N값이 11이므로 모두 구해둔 뒤 사용한다.

        for(int i=4; i<=11; i++){
            dp[i]=dp[i-3]+dp[i-2]+dp[i-1];
        }

3.4. 결과 출력

• 각 테스트 케이스에 해당하는 경우의 수 출력

        for(int i=0; i<T; i++){
            int N=Integer.parseInt(br.readLine());
            System.out.println(dp[N]);
        }

4. 전체코드

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[] dp=new int[12];
        dp[0]=0;
        dp[1]=1;
        dp[2]=2;
        dp[3]=4;
        for(int i=4; i<=11; i++){
            dp[i]=dp[i-3]+dp[i-2]+dp[i-1];
        }
        for(int i=0; i<T; i++){
            int N=Integer.parseInt(br.readLine());
            System.out.println(dp[N]);
        }
    }
}