백준 2293번 [동전 1](C++) -yes6686- 티스토리

백준 문제 풀이: 2293 [동전 1]

---

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

문제 설명:

n가지 종류의 동전이 주어졌을 때, 주어진 동전들을 사용하여 가치의 합이 k원이 되는 경우의 수를 구하는 문제입니다.

동전의 순서는 상관없으며, 각 동전은 무한정 사용할 수 있습니다.

---

문제 해결 코드

#include <iostream>
using namespace std;

int coins[101];  // 동전의 가치를 저장하는 배열
int dp[10001];   // 가치 합이 k원이 되는 경우의 수를 저장하는 배열

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

    int n, k; // n: 동전의 종류, k: 목표 금액
    cin >> n >> k;

    // 동전 입력
    for (int i = 0; i < n; i++) {
        cin >> coins[i];
    }

    // 동적 프로그래밍 초기화
    dp[0] = 1; // 아무 동전도 사용하지 않는 경우는 1가지

    // 동전 순회
    for (int i = 0; i < n; i++) {
        for (int j = coins[i]; j <= k; j++) {
            dp[j] += dp[j - coins[i]];
        }
    }

    // 결과 출력
    cout << dp[k] << '\n';

    return 0;
}

---

코드 설명

• 핵심 알고리즘: 동적 프로그래밍을 사용하여, 각 동전의 가치를 기반으로 가치 합을 계산합니다. 문제의 특징(동전을 무한히 사용할 수 있음)에 따라 배낭 문제의 변형으로 접근합니다.
• 구현 세부사항:
  • dp[j]: 가치 합이 j가 되는 경우의 수를 저장합니다.
  • dp[j] += dp[j - coins[i]]: 동전 coins[i]를 추가하여 가치 j를 만들 수 있는 경우를 추가합니다.
  • 동전은 오름차순으로 처리하여 순서가 다른 경우를 중복 계산하지 않도록 합니다.
• 시간 복잡도 분석: O(n × k)
  • n: 동전의 종류
  • k: 목표 금액
  이중 루프를 사용하므로 시간 복잡도는 동전 수와 목표 금액의 곱입니다.

---

결과

동적 프로그래밍을 사용하여 주어진 동전들로 가치 합이 k가 되는 경우의 수를 효율적으로 계산합니다.

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