백준 15988번 [1, 2, 3 더하기 3](C++) -yes6686- 티스토리

백준 문제 풀이: 15988 [1, 2, 3 더하기 3]

---

문제 링크: https://www.acmicpc.net/problem/15988

문제 설명:

정수 N을 1, 2, 3의 합으로 나타내는 방법의 수를 구하는 문제입니다. 결과는 1,000,000,009로 나눈 나머지를 출력해야 합니다.

• 예를 들어, N=4일 때 가능한 방법은 다음과 같습니다: 1+1+1+1, 1+1+2, 1+2+1, 2+1+1, 2+2, 1+3, 3+1 (총 7가지).
• 동적 프로그래밍을 활용해 효율적으로 풀이합니다.

---

문제 해결 코드

#include <iostream>
#define MOD 1000000009
#define MAX 1000001
using namespace std;

long long int dp[MAX]; // 각 숫자를 1, 2, 3의 합으로 나타내는 경우의 수를 저장하는 배열

int main() {
    ios::sync_with_stdio(false);
    cin.tie(NULL);

    int T; // 테스트 케이스 수
    cin >> T;

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

    // 점화식 계산
    for (int i = 4; i < MAX; i++) {
        dp[i] = (dp[i - 1] + dp[i - 2] + dp[i - 3]) % MOD;
    }

    // 테스트 케이스 처리
    while (T--) {
        int n;
        cin >> n;
        cout << dp[n] << '\n'; // n을 1, 2, 3의 합으로 나타내는 방법의 수 출력
    }

    return 0;
}

---

코드 설명

• 핵심 알고리즘: 동적 프로그래밍을 사용하여 N을 1, 2, 3의 합으로 나타내는 경우의 수를 계산합니다.
• 구현 세부사항:
  • dp[i]: 정수 i를 1, 2, 3의 합으로 나타내는 방법의 수
  • 점화식: dp[i] = (dp[i-1] + dp[i-2] + dp[i-3]) % MOD
  • MOD 연산을 통해 값이 커지는 것을 방지합니다.
• 시간 복잡도 분석: O(MAX + T)
  • DP 배열 초기화: O(MAX)
  • 테스트 케이스 처리: O(T)
  전체 시간 복잡도는 O(MAX + T)로 매우 효율적입니다.

---

결과

테스트 케이스마다 정수 N을 1, 2, 3의 합으로 나타내는 방법의 수를 정확히 계산합니다. 동적 프로그래밍을 활용해 효율적으로 풀이했습니다.

다른 접근 방식이나 개선 사항이 있다면 댓글로 공유 부탁드립니다!