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

난이도

실버 3

문제

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

풀이

1. 진짜 문제 정의
   주어진 N에 대해서 N을 1,2,3의 합으로 표현하는 경우의 수

2. 가짜 문제 정의
   Dy[i]=i를 1,2,3의 합으로 표현하는 경우의 수

3. 초기값 구하기
   D[1] = 1
   D[2] = 2
   D[3] = 4

4. 점화식 찾기
   정수 4일 때
   1+1+1+1, 1+2+1, 2+1+1, 3+1 -> 3을 1,2,3의 합으로 나타내는 방법 +1 = D[3]
   1+1+2, 2+2 -> 2을 1,2,3 의 합으로 나타내는 방법 +2 = D[2]
   1+3 -> 1을 1,2,3의 합으로 나타내는 방법 +3 = D[1]

따라서
D[4] = D[3] + D[2] + D[1]
D[i] = D[i-1] + D[i-2] + D[i-3]

코드

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

// 9095번 1,2,3 더하기
public class boj_4_9095 {
    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[11];
        dp[1] = 1;
        dp[2] = 2;
        dp[3] = 4;

        while (t-- > 0) {
            int n = Integer.parseInt(br.readLine());

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

            System.out.println(dp[n]);

        }
    }
}