[ 백준-2293번 / DP ] 동전 1

1. 문제

---

 

2293번: 동전 1

문제

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

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

입력

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

출력

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

예제 입력 1 복사

3 10 1 2 5

예제 출력 1 복사

10

 

 

 

 

2. 소스코드

---

1회차 - 20/05/23

 

- 문제 조건이 까다롭다. 메모리 제한이 4MB. 시간 제한 0.5초. 시간제한은 DP로 풀라는 거니까 그렇다 쳐도. 메모리 제한 때문에 2차원 배열, 재귀를 사용할 수 없다.

- 따라서 bottom - up 풀이만 가능함.

- dp[ j - 동전값 ] 을 생각해 내는게 문제의 전부인듯.

 

#include <iostream>
using namespace std;
int dp[10000 + 1];
int cost[100 + 1];
int n, k;

int main(void){
 
    cin >> n >> k;
    for (int i = 1; i <= n; i++) 
        cin >> cost[i];

   // 2원을 만들어야되는데 2원짜리 동전이 있는 경우  j - cost[i] = 0이된다.
   // 따라서 dp[0]을 1로 초기화 시켜주어야함.
    dp[0] = 1;  
   
    for (int i = 1; i <= n; i++) { // 동전의 수만큼
        for (int j = cost[i]; j <= k; j++) { // j 는 cost[i]로 초기화 되어야함.
            if (j-cost[i] >= 0) dp[j] += dp[j - cost[i]];
        }
    }

    cout << dp[k] << '\n';
    return 0;
}

 

- 배열을 하나만 쓰고도 만들 수 있다. 어차피 dp 값은 += 로 누적이기 때문에!

#include<stdio.h>

int main()
{
	int n, target, i, j;
	int dp[10001] = { 0, };
	int cost;

	scanf("%d%d", &n, &target); 

	dp[0] = 1;
	for (i = 0; i < n; i++)
	{
		scanf("%d", &cost);

		for (j = cost; j <= target; j++) {
            if (j - cost >= 0)
                dp[j] += dp[j - cost];
		}
	}

	printf("%d", dp[target]);
	return 0;
}