백준 2293 C++ - 동전1

Intro

문제해결 및 소스코드

#include <iostream>

using namespace std;

/*
						<문제해결>
				- n개의 동전이 있을때, 첫번째 동전부터 시작하여 그 동전까지있을 때 목표액 k를 달성하는 경우의수를 dp[n]이라고 정의
				- 예시) 3개의 동전 coins[1, 2, 5] 가 있을때, 목표액 10을 달성하는 경우의수는

				기저값 dp[0] = 1 로 설정 -> 0원을 달성할 순 없지만 0원을 달성하는것은 아무동전도 사용하지 않은 경우라고 생각
				
				dp
				목표액	k	0	1	2	3	4	5	6	7	8	9	10
				동전	1원	1	1	1	1	1	1	1	1	1	1	1	=>	1원으로 목표액 1~10원을 달성하는 경우는 1가지씩 뿐
						2원	1	1	2	2	3	3	4	4	5	5	6	=>	2원으로 목표액 1원을 달성할수는 없음 --> 1원으로 1원을 달성하는 경우만 존재
																			2원으로 목표액 2~10원을 달성하는 경우는 1원으로 2~10원을 달성하는 경우와
																			1,2원으로 0~8원을 달성하는 경우의수를 합한것.
						3원	1	1	2	2	3	4	5	6	7	8	10

				따라서 새롭게 업데이트할 dp[i]는 이전의 dp[i]와 이전의 dp[i-coins[i]]의 합과 같다.
*/

int dp[100001];					// dp[i] : i원을 달성하는 경우의 수
int coins[101];					// 동전의 가치를 담을 변수

int main()
{
	int n, k;
	cin >> n >> k;

	// 동전 입력
	for (int i = 1;i <= n;i++)
	{
		cin >> coins[i];
	}

	dp[0] = 1;					// 0원을 달성하는 경우는 아무것도 선택하지 않았을 경우라고 생각

	for (int i = 1;i <= n;i++)		
	{	
		for (int j = coins[i];j <= k;j++)	
		{
			dp[j] = dp[j] + dp[j - coins[i]];
		}
	}

	cout << dp[k];
}