[백준][JAVA] - 1, 2, 3 더하기(9095)

문제 소개

🥈 문제 레벨 : 실버3
🔔 문제 유형 : 다이나믹 프로그래밍
💬 풀이 언어 : JAVA
⏱️ 풀이 시간 : 30분
🖇️ 문제 링크 : 백준 문제 링크

📝 문제

정수 4를 1, 2, 3의 합으로 나타내는 방법은 총 7가지가 있다. 합을 나타낼 때는 수를 1개 이상 사용해야 한다.

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

정수 n이 주어졌을 때, n을 1, 2, 3의 합으로 나타내는 방법의 수를 구하는 프로그램을 작성하시오.

🤔 문제 분석

문제에서 언급한 것과 같이 1, 2, 3만을 사용해서 값을 표현할 수 있는 경우의 수를 구해야 한다.

0부터 3까지 각각 사용할 수 있는 경우의 수를 확인해보면 아래와 같다.

구분	경우의 수	조합
1	1개	1
2	2개	1 + 1 / 2
3	4개	1 + 1 + 1 / 1 + 2 / 2 + 1 / 3

1, 2, 3을 이용해 4를 만들 수 있는 경우의 수를 보면 아래와 같다.

• 1을 이용한 조합 : 1개
• 2을 이용한 조합 : 2개
• 3을 이용한 조합 : 4개

4 + 2 + 1로 총 7개의 경우의 수로 구할 수 있다.

5의 경우를 보면 아래로 나눌 수 있다.

• 2을 이용한 조합 : 2개
• 3을 이용한 조합 : 4개
• 4를 이용한 조합 : 7개

즉, (n - 3) + (n - 2) + (n - 1)을 통해 값을 구할 수 있다.

1, 2, 3에 대한 값이 필요하므로 미리 값을 메모제이션(memoization)을 한 뒤, 풀이해야 한다.

😎 최종 코드

메모리 : 11480 KB
시간 : 76 ms

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));

        int T = Integer.parseInt(br.readLine());
        int[] dp;

        while (T-- > 0) {
            int n = Integer.parseInt(br.readLine());
            // n의 값은 11 미만이라고 되어있기 때문에 11로 초기화
            dp = new int[11];
            dp[0] = 0;
            dp[1] = 1;
            dp[2] = 2;
            dp[3] = 4;

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

            bw.append(dp[n] + "\n");

        }

        bw.flush();
        bw.close();
        br.close();
    }
}