[백준] 9095번 - 1, 2, 3 더하기 java

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

 

난이도 : S3

Tag : DP

풀이 일자 : 2025-03-07

---

문제 탐색하기

T : 테스트 케이스 수

n : 1,2,3의 합으로 나타낼 수 (1 <= n <= 11)

 

이 문제는 정수 n을 1, 2, 3의 합으로 나타내는 모든 경우의 수를 구하는 문제입니다.

즉, 주어진 숫자 n을 만들 수 있는 서로 다른 합의 방법을 찾는 것이 핵심입니다.

 

예를 들어, n = 4일 때 가능한 조합은 다음과 같습니다.

1. 1+1+1+1
2. 1+1+2
3. 1+2+1
4. 2+1+1
5. 2+2
6. 1+3
7. 3+1

가능한 시간복잡도

이 문제는 n <= 11이므로 브루트포스로 해결할 수도 있지만,

이를 일반화하여 n이 커질 때의 시간복잡도를 고려하면 완전 탐색O(3^n)은 비효율적입니다.
예를 들어, n=20이면 경우의 수가 121415개이고,  O(3^20) ≈ 35억 번의 연산이 필요하여 현실적으로 해결 불가능합니다.

 

반면, DP를 사용하면 O(n)의 시간복잡도로 해결할 수 있습니다.

왜 DP를 쓸 수 있는가?

DP를 사용하려면 다음 조건을 만족해야 합니다.

1. 부분 문제 최적화: 큰 문제를 작은 문제들의 조합으로 해결할 수 있어야 합니다.
   • 예를 들어, dp[5]는 dp[4], dp[3], dp[2]의 값을 이용해서 구할 수 있습니다.
   • dp[5] = dp[4] + dp[3] + dp[2] = 7 + 4 + 2 = 13
2. 중복되는 부분 문제: 동일한 연산을 여러 번 반복하지 않고 저장하여 재사용할 수 있어야 합니다.
   • 예를 들어, dp[10]을 구할 때 dp[9], dp[8], dp[7]이 필요하고, dp[9]을 구할 때 dp[8], dp[7], dp[6]이 필요합니다.
   • 따라서, 한 번 계산한 값을 저장해두면 같은 연산을 반복하지 않아 효율적으로 계산할 수 있습니다.
   이 문제는 위의 두 조건을 만족하므로 DP를 활용하여 해결할 수 있습니다.

알고리즘 선택

DP를 사용하겠습니다.

우리는 숫자 n을 만들기 위해 1, 2, 3 중 하나를 마지막으로 사용한 경우로 나눌 수 있습니다.

즉, 어떤 숫자 n을 만들기 위해서는 마지막에 더해진 숫자가 1, 2, 또는 3 이어야 합니다.

• 마지막 숫자가 1인 경우 → dp[n-1]
• 마지막 숫자가 2인 경우 → dp[n-2]
• 마지막 숫자가 3인 경우 → dp[n-3]

모든 경우는 서로 중복되지 않고, n을 만드는 모든 조합을 포함하므로 다음과 같은 점화식이 성립합니다

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

기저 사례 

dp[1], dp[2], dp[3]의 값을 직접 구해서 점화식을 검증해 볼 수 있습니다.

1. dp[1] = 1 (1을 만들 수 있는 방법: {1})
2. dp[2] = 2 (2를 만들 수 있는 방법: {1+1, 2})
3. dp[3] = 4 (3을 만들 수 있는 방법: {1+1+1, 1+2, 2+1, 3})

이를 통해 dp[4] = dp[3] + dp[2] + dp[1] = 4 + 2 + 1 = 7이 성립하는 것을 확인할 수 있습니다.

---

코드 설계하기

1. 입력값을 받습니다.
2. DP 배열을 선언하고 초기값을 설정합니다.
3. 점화식을 이용해 DP 테이블을 채웁니다.
4. 주어진 n 값에 대해 결과를 출력합니다.

---

정답코드

import java.util.*;

class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        final int MAX_NUM = 11;
        int t = sc.nextInt();
        int[] dp = new int[MAX_NUM+1]; 

        dp[1] = 1;
        dp[2] = 2;
        dp[3] = 4;

        for(int i=4; i<MAX_NUM+1; i++){
            dp[i] = dp[i-3] + dp[i-2] + dp[i-1];
        }
        
        for(int i=0; i<t; i++){
            int n =sc.nextInt();
            System.out.println(dp[n]);
        }
        sc.close();
    }
}