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

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

---

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

문제 설명:

정수 n(1 ≤ n ≤ 10)이 주어졌을 때, 1, 2, 3의 합으로 n을 만들 수 있는 모든 방법의 수를 구하는 문제입니다. 각 숫자는 여러 번 사용될 수 있습니다.

---

문제 해결 코드

#include <iostream>
using namespace std;

int dp[10];

int main() {
    int T;
    cin >> T;
    int n;

    // 초기값 설정
    dp[1] = 1;
    dp[2] = 2;
    dp[3] = 4;

    // 동적 프로그래밍으로 dp 배열 계산
    for (int i = 4; i <= 10; i++) {
        dp[i] = dp[i - 1] + dp[i - 2] + dp[i - 3];
    }

    // 테스트 케이스 처리
    while (T--) {
        cin >> n;
        cout << dp[n] << '\n';
    }
    return 0;
}

---

코드 설명

• 핵심 알고리즘: 동적 프로그래밍을 이용하여 1, 2, 3의 합으로 정수를 표현하는 경우의 수를 계산합니다.
• 구현 세부사항:
  • dp[i]는 정수 i를 1, 2, 3의 합으로 나타내는 모든 방법의 수를 저장합니다.
  • 점화식: dp[i] = dp[i - 1] + dp[i - 2] + dp[i - 3]
  • 초기값: dp[1] = 1, dp[2] = 2, dp[3] = 4
• 시간 복잡도: O(n)
  • dp 배열 계산: O(10) (최대 10까지)
  • 테스트 케이스 처리: O(T)

---

결과

주어진 테스트 케이스에 대해 정수 n을 1, 2, 3의 합으로 나타낼 수 있는 모든 방법의 수를 출력합니다. 동적 프로그래밍을 사용하여 효율적으로 계산하였습니다.

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