BOJ_15989 : 1, 2, 3 더하기 4

👉 문제링크

---

---

🔸 문제 분석 🔸

• 1, 2, 3의 덧셈으로 n을 만들 수 있는 조합의 수를 출력한다.

🔸 문제 풀이 🔸

• 다이나믹 프로그래밍 문제로, dp[n]은 n을 만드는 조합의 수이다.
• 중복을 제거하기 위해 1로 한바퀴, 2로 한바퀴, 3으로 한바퀴 각각 dp를 돌려야 한다.

🔸 코드 🔸

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

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        StringBuilder sb = new StringBuilder();

        int[] dp = new int[10_001];
        dp[0] = 1;
        for (int i = 1; i <= 3; i++) {
            for (int j = i; j < 10_001; j++) {
                dp[j] += dp[j - i];
            }
        }

        int T = Integer.parseInt(br.readLine());
        for (int t = 1; t <= T; t++) {
            int n = Integer.parseInt(br.readLine());
            sb.append(dp[n]).append('\n');
        }
        bw.write(sb.toString());
        bw.flush();
    }
}

🔸 코드 해석 🔸

• dp배열을 최댓값인 10,000까지 먼저 채운다.
  • dp[0] 만 초기값으로 1을 넣어준다.
  • 1로 한바퀴, 2로 한바퀴, 3으로 한바퀴 dp 배열을 채워 중복을 피한다.

---

🔸 end 🔸

• 중복을 제거하는 방법을 많이 고민했던 것 같다.
• 생각보다 풀이 결과는 간단해서 이런 종류에 대한 연습이 부족했던 것 같다.