백준 2293번 : 동전 1 (C 언어)

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

2293번: 동전 1

Code:

#include <stdio.h>
 
int main() {
    int n, k;
    scanf("%d %d", &n, &k);
    int arr[10001] = { 0, };
    int dp[10001] = { 0, };
    for (int i = 1; i <= n; i++)
    {
        scanf("%d", &arr[i]);
    }
    dp[0] = 1;
    for (int i = 1; i <= n; i++) {
        for (int j = arr[i]; j <= k; j++) {
            dp[j] += dp[j - arr[i]];
        }
    }
    printf("%d", dp[k]);
}

문제풀이:

1. 문제 설명

n가지 종류의 동전이 주어지고, 이 동전을 적당히 사용하여 그 가치의 합이 k원이 되도록 만들고 싶습니다. 이 때, 가능한 동전 조합의 경우의 수를 구하는 문제입니다. 동전의 구성이 같은데 순서만 다른 경우는 같은 경우로 간주합니다.

2. 코드 설명

주어진 코드는 동적 계획법(Dynamic Programming)을 사용하여 동전 조합의 경우의 수를 구합니다.

1. 입력으로 n (동전의 종류 수)와 k (목표 합계 금액)를 받습니다.
2. n개의 동전의 가치를 입력받아 arr 배열에 저장합니다.
3. dp 배열을 초기화합니다. dp[i]는 가치의 합이 i원이 되도록 만들 수 있는 경우의 수를 저장하는 배열입니다.
4. 초기 상태로 dp[0]은 1로 설정합니다. 가치의 합이 0원인 경우는 동전을 사용하지 않는 경우로 1가지의 조합이 가능합니다.
5. 동적 계획법을 사용하여 dp 배열을 채웁니다. 각 동전의 가치를 하나씩 추가해가면서 dp 배열을 갱신합니다. 이때, dp[j]는 dp[j-arr[i]]에 해당 동전을 추가한 경우와 이전까지의 조합 수(dp[j])를 더한 값입니다. 이를 통해 가능한 동전 조합의 경우의 수를 누적하여 계산합니다.
6. dp[k]를 출력합니다. 이 값은 동전 조합의 경우의 수입니다.