동전 1 성공

시간 제한	메모리 제한	제출	정답	맞은 사람	정답 비율
2 초	4 MB	21984	9022	6685	41.763%

문제

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

사용한 동전의 구성이 같은데, 순서만 다른 것은 같은 경우이다.

입력

첫째 줄에 n, k가 주어진다. (1 ≤ n ≤ 100, 1 ≤ k ≤ 10,000) 다음 n개의 줄에는 각각의 동전의 가치가 주어진다. 동전의 가치는 100,000보다 작거나 같은 자연수이다.

출력

첫째 줄에 경우의 수를 출력한다. 경우의 수는 2^31보다 작다.

예제 입력 1

3 10 1 2 5

예제 출력 1

출처

어색한 표현을 찾은 사람: dbfldkfdbgml
빠진 조건을 찾은 사람: goodcrane3
데이터를 추가한 사람: jh05013

알고리즘 분류

내 소스

문제 번호	결과	메모리	시간	언어	코드 길이
2293	맞았습니다!!	1988	0	C++14	555

#include <iostream>
using namespace std;

int main() {
    int i;
    int j;
    int tmp;
    int n;
    int k;
    int *arr;
    int *answer;
    
    cin >> n;
    cin >> k;
    
    arr = new int[n];
    answer = new int[k+1](); // 동적할당 후 0으로 초기화
    
    for(i=0; i<n; i++){
        cin >> arr[i];
    }
    
    for(i=0; i<n; i++){
        tmp = arr[i];
        answer[tmp]++;
        for(j=tmp+1; j<=k; j++){
            answer[j] += answer[j-tmp];
        }
    }
    
    cout << answer[k];
    
    return 0;
}

Big-O

시간 복잡도 : O(N^2)

공간 복잡도 : O(N)

솔루션

- 1원만 사용해서 10원을 만드는 경우의 수

1원	2원	3원	4원	5원	6원	7원	8원	9원	10원
1가지	1가지	1가지	1가지	1가지	1가지	1가지	1가지	1가지	1가지

- 1, 2원 사용해서 10원을 만드는 경우의 수

1원	2원	3원	4원	5원	6원	7원	8원	9원	10원
1가지	2가지	2가지	3가지	3가지	4가지	4가지	5가지	5가지	6가지

찾을 수 있는 패턴

4원을 만들 때는 2원을 만드는 경우의 수(2)를 현재 경우의 수(1)에 더했다.

5원을 만들 때는 3원을 만드는 경우의 수(2)를 현재 경우의 수(1)에 더했다.

6원을 만들 때는 4원을 만드는 경우의 수(3)을 현재 경우의 수 (1)에 더했다.

-> N원을 사용해서 M원을 만들 때는 M-N원을 만드는 경우의 수를 현재 경우의 수에 더했다.

M-N원을 만드는 경우의 수를 더하는 이유

6원을 만들기 위해 2원 / 4원으로 쪼갤 수 있다.

4원을 만드는 경우의 수

1 1 1 1 / 1 1 2 / 2 2 - 총 3가지

6원을 만드는 경우의 수

1 1 1 1 1 1 / 1 1 1 1 +2 / 1 1 2 +2 / 2 2 +2 - 총 4가지

-> N원을 사용하지 않는 경우의 수 + N원을 이용하여 M-N원을 만드는 경우의 수 = N원을 사용하는 경우의 수

- 1, 2, 5원 사용해서 10원을 만드는 경우의 수

1원	2원	3원	4원	5원	6원	7원	8원	9원	10원
1가지	2가지	2가지	3가지	4가지	5가지	6가지	7가지	8가지	10가지

저작자표시 (새창열림)