📌 [코딩테스트] 백준 9095번 1, 2, 3 더하기 풀이 - 자바

🎯 1, 2, 3 더하기 문제란?

프로그래밍 문제를 풀다 보면 특정 수를 만드는 방법의 개수를 세는 문제를 자주 접하게 됩니다. 이번에 다룰 문제는 정수 n을 1, 2, 3의 합으로 나타내는 방법의 수를 구하는 문제입니다.

예를 들어 n = 4인 경우, 다음과 같은 7가지 방법이 존재합니다.

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

이제 이 문제를 효율적으로 해결할 방법을 알아보겠습니다! 🚀

---

1️⃣ 문제 이해 및 접근 방법

이 문제를 풀기 위해 **동적 계획법(Dynamic Programming, DP)**을 사용합니다.
dp[n]을 정수 n을 1, 2, 3의 합으로 나타내는 방법의 수라고 정의하면, 점화식은 다음과 같이 세울 수 있습니다.

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

 

이유:

• dp[n-1]에서 +1을 추가하면 dp[n]이 됨
• dp[n-2]에서 +2를 추가하면 dp[n]이 됨
• dp[n-3]에서 +3을 추가하면 dp[n]이 됨

---

2️⃣ 코드 구현 (Java)

import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int T = scanner.nextInt(); // 테스트 케이스 개수

        // n이 11보다 작다고 했으므로, 미리 DP 배열을 선언
        int[] dp = new int[11];

        // 초기값 설정
        dp[1] = 1; // (1)
        dp[2] = 2; // (1+1, 2)
        dp[3] = 4; // (1+1+1, 1+2, 2+1, 3)

        // DP 배열 채우기
        for (int i = 4; i <= 10; i++) {
            dp[i] = dp[i - 1] + dp[i - 2] + dp[i - 3];
        }

        // 테스트 케이스 실행
        for (int i = 0; i < T; i++) {
            int n = scanner.nextInt();
            System.out.println(dp[n]);
        }

        scanner.close();
    }
}

---

3️⃣ 코드 설명

1. 입력값 받기
   • Scanner를 사용하여 테스트 케이스 개수 T를 입력받습니다.
2. DP 배열 초기화
   • dp[1] = 1 → (1)
   • dp[2] = 2 → (1+1, 2)
   • dp[3] = 4 → (1+1+1, 1+2, 2+1, 3)
3. 점화식을 이용해 DP 배열 채우기
   • dp[n] = dp[n-1] + dp[n-2] + dp[n-3]를 이용해 dp[10]까지 미리 계산합니다.
4. 테스트 케이스별 결과 출력
   • O(1)의 시간 복잡도로 빠르게 결과를 출력합니다.

---

4️⃣ 시간 복잡도 분석

• DP 테이블을 미리 채워둠 → O(n) (n=10)
• 각 테스트 케이스에서 바로 결과 출력 → O(1)
• 최종 시간 복잡도: O(n) (최대 O(10), 매우 빠름)

---

5️⃣ 실행 예제 

✅ 입력 예시

 

3
4
7
10

✅ 출력 예시

7
44
274

---

🚀 최종 정리

💡 이번 글에서 배운 점

1. **동적 계획법(DP)**을 사용하면 반복적인 연산을 줄이고 빠르게 계산할 수 있습니다.
2. dp[n] = dp[n-1] + dp[n-2] + dp[n-3]의 점화식을 활용하면 문제를 효율적으로 해결할 수 있습니다.
3. 미리 DP 테이블을 계산해두면 테스트 케이스가 많아도 빠르게 결과를 출력할 수 있습니다.

이제 여러분도 DP 문제를 만났을 때 점화식을 떠올리며 문제를 해결해보세요! 🔥🚀