[백준] 9095번 : 1, 2, 3 더하기 – JAVA [자바]

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

9095번: 1, 2, 3 더하기

 

---

• 문제

 

 

---

• 문제 풀이

백준 9095번 1, 2, 3 더하기는 실버 3 난이도의 DP 문제이다. 이 문제에서는 테스트 케이스의 개수 T가 주어진다. 그리고 각 테스트 케이스마다 정수 n이 주어진다. 이때 n을 1, 2, 3의 합으로 나타내는 방법의 수를 출력하면 된다.

 

우선 예를 들어보겠다.

 

n = 1

• 1

∴  1가지

 

 

n = 2

• 1 + 1
• 2

∴  2가지

 

 

n = 3

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

∴  3가지

 

 

n = 4

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

∴ 7가지

 

여기서 보면 패턴을 찾을 수 있다. dp [i]는 숫자 i를 1, 2, 3의 합으로 나타낼 수 있는 방법의 수라고 하겠다. 여기서 보면 dp [i]는 다음과 같다.

 

dp [i] = dp [i - 1] + dp [i - 2] + dp [i - 3]

 

따라서 이 점을 이용해서 for-loop을 이용해서 Bottom-up 방식으로 이 문제를 풀 수 있다.

 

자세한 코드는 밑에 있는 코드를 참고하면 되겠다.

 

---

• 코드

 

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[12];
        dp[1] = 1;
        dp[2] = 2;
        dp[3] = 4;
        StringBuilder sb = new StringBuilder();
        for (int i = 4; i <= 11; i++) {
            dp[i] = dp[i-1] + dp[i-2] + dp[i-3];
        }
        for (int i = 0; i < t; i++) {
            int n = Integer.parseInt(br.readLine());
            sb.append(dp[n] + "\n");
        }
        System.out.print(sb);
    }
}