접근방법
동전을 전부 배열에 넣어놓고 하나씩 꺼내면서 전체 배열을 갱신한다.
배열을 갱신할 때 해당 동전의 크기만큼의 앞의 원소를 해당 원소에 더한다.
예를 들어, 동전의 크기가 2일 때 a[i]=a[i]+a[i-2]
왜냐하면 동전의 크기가 2이면 i=2일 때는 동전 하나로 나타낼 수 있지만 i=4일 때는 동전 두 개로 나타내야 하기 때문이다.
코드
#include <iostream>
using namespace std;
int main()
{
cin.tie(NULL);
ios_base::sync_with_stdio(false);
int n, k;
int coin[101], arr[10001] = { 0, };
cin >> n >> k;
for (int i = 0; i < n; i++)
cin >> coin[i];
for (int i = 0; i < n; i++){
if (coin[i] > k)continue;
arr[coin[i]] += 1;
for (int j = coin[i]+1; j <= k; j++){
arr[j] += arr[j - coin[i]];
}
}
cout << arr[k];
}
'코딩테스트 > 백준' 카테고리의 다른 글
백준 1202 : 보석 도둑 (0) | 2021.06.16 |
---|---|
백준 10158 : 개미 (0) | 2021.04.18 |
백준 2580 : 스도쿠 (0) | 2020.09.14 |
백준 2108 : 통계학 (0) | 2020.09.05 |
백준 2751 : 수 정렬하기 2 (0) | 2020.08.21 |