본문 바로가기

컴퓨터/Online Judge

[acmicpc.net] 2293 동전 1

반응형

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


문제 내용

n가지 종류의 동전이 있다. 각각의 동전이 나타내는 가치는 다르다. 이 동전들을 적당히 사용해서, 그 가치의 합이 k원이 되도록 하고 싶다. 그 경우의 수를 구하시오. (각각의 동전은 몇 개라도 사용할 수 있다.)


소스코드


#include <iostream>
using namespace std;
 
int main() {
    int n, k;
    int *value;
    int **result;
    cin >> n >> k;
    value = new int[n];
    result = new int*[2];
    for(int i=0; i<n; i++){
        cin >> value[i];
    }
    for(int i=0; i<2; i++){
        result[i] = new int[k+1];
    }
    result[0][0] = 1;
    for(int i=1; i<=n; i++){
        for(int j=0; j<=k; j++){
            result[i&1][j] = result[(i+1)&1][j] + (j>=value[i-1] ? result[i&1][j-value[i-1]] : 0);
        }
    }
    cout << result[n&1][k];
    return 0;
}



반응형

'컴퓨터 > Online Judge' 카테고리의 다른 글

[acmicpc.net] 11726 2×n 타일링  (0) 2016.09.21
[acmicpc.net] 1932 숫자삼각형  (0) 2016.09.18
[acmicpc.net] 2167 2차원 배열의 합  (0) 2016.09.11
[acmicpc.net] 2579 계단 오르기  (0) 2016.09.09
[acmicpc.net] 2193 이친수  (0) 2016.09.08