백준[2293] 동전 1

아이디어

• [DP]를 다룰줄 안다

접근방식

1. 동전의 값을 벡터에 저장해준다
2. DP를 이용하되, 하나의 동전을 하나씩 사용하는 경우마다 단계적으로 조사한다.
3. 점화식은 '지금 계산하는 경우의수 = 이전 동전으로만 가능한 경우의 수 + 새로 넣을 동전까지 포함한 경우의수' 로 한다

#include <iostream>
#include <vector>
#include <algorithm>
#include <utility>
#include <math.h>
#include <queue>

#define MAX 987654321

using namespace std;


//(coin 번호, 총합 금액)
int arr[100001];

int main()
{
	int coin_cnt, target_won; scanf("%d %d", &coin_cnt, &target_won);
	vector<int> coins;

	for (int i = 0; i < coin_cnt; i++)
	{
		int num; scanf("%d", &num);
		coins.push_back(num);
	}

	//하나씩 동전을 추가할때마다 나오는 경우를 dp로 점점 저장해준다
	for (int now = 0; now < coins.size(); now++)
	{
		//지금부터 계산하려는 동전의 값에 경우의 수 1을 넣는다
		int coin = coins[now];
		arr[coin] += 1;

		// 이번에 새로 동전을 넣은 경우의수 + 이전 동전으로만 가능한 경우의 수
		for (int now_won = 1; now_won <= target_won; now_won++)
		{
			if (now_won - coin >= 0) arr[now_won] += arr[now_won - coin];
		}
	}

	printf("%d\n", arr[target_won]);
	
	return 0;
}

평가

DP로 중복되는 경우를 어떻게 제거할 수 있는지 물어보는 문제.
저는 중복되는 경우를 해결하는 법을 찾기가 어려워 굉장히 고민했습니다. DP 문제를 자주 풀어 본 사람이라면 충분히 해결할 수 있는 문제라고 생각합니다.

• 배울점 : DP의 점화식을 잘 세워야 한다