[백준 / java] 9095 : 1,2,3 더하기

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

package boj9095;

import java.io.*;
import java.util.*;

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[11];
        dp[1] = 1;
        dp[2] = 2;
        dp[3] = 4;

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

        while(T --> 0){
            System.out.println(dp[Integer.parseInt(br.readLine())]);
        }

    }
}

2 : 2가지

• 1 + 1
• 2

3 : 4가지

• 1 + 1 + 1
• 1 + 2
• 2 + 1
• 3

4 : 7가지

• 1 + 1 + 1 + 1
• 1 + 1 + 2
• 1 + 2 + 1
• 2 + 1 + 1
• 2 + 2
• 3 + 1
• 1 + 3

4를 쪼개어 보았을때 1 + 3, 2 + 2, 3 + 1 세가지로 볼 수 있다

→ 1을 만드는 경우 + 3, 2를 만드는 경우 + 2, 3을 만드는 경우 + 1

• (1) + 3
• (1 + 1 / 2) + 2
• (1 + 1 + 1 / 1 + 2 / 2 + 1 / 3) + 1

→ 단순 더하기이므로 각각의 경우의 수에는 변화가 없다

→ 즉, dp[4] = dp[3] + dp[2] + dp[1]

5또한 마찬가지 → 4 + 1, 3 + 2, 2 + 3 (4는 더할 수 없으므로 1 + 4는 해당 x)

→ dp[5] = dp[4] + dp[3] + dp[2]

dp 너무 어렵다..