거스름돈

https://programmers.co.kr/learn/courses/30/lessons/12907

이문제 못풀었음.

#include <string>
#include <vector>
#include <algorithm>
using namespace std;

int answer(0);

void dfs(int nowM, int order, vector<int> & money)
{
	for (int i = order; i < money.size(); i++)
	{
		if (nowM - money[i] == 0)
		{
			answer++;
		}
		else if (nowM - money[i]> 0)
		{
			dfs(nowM - money[i], i, money);
		}
		else
		{
			return;
		}
	}
}

int solution(int n, vector<int> money) {

	sort(money.begin(), money.end(), [](int a, int b) {
		return a < b;
	});

	dfs(n, 0, money);

	return answer;
}

처음에 DFS로 풀었는데 이랬을 경우 시간초과 뜸.
DP로 푼 풀이

#include <string>
#include <vector>

using namespace std;

long long dp[100001];

int solution(int n, vector<int> money) {
	int answer = 0;

	dp[0] = 1;//0원을 만드는 경우는 1개

	for (int i = money[0]; i <= n; i += money[0])//젤 작은 돈만 써서 만드는 경우들 기본 셋팅
	{
		dp[i] = 1;
	}

	for (int i = 1; i < money.size(); i++)//쓰고 싶은 돈
	{
		for (int j = 0; j <= n; j++)
		{
			if (j >= money[i])//어차피 이 금액보다 작은놈은 못쓰니까 처리~
				dp[j] += dp[j - money[i]] % 1000000007;
			//이 동전 한개 써서 만들 수 있는 모든 경우의 수 쁠러쓰~
			//어차피 작은 값부터 순차적으로 올라가니까 이전 dp를 더하기만 하면댐
		}
	}
	answer = dp[n];
	return answer;
}


int main() {

	int n = 5;
	vector<int> vTemp={ 1,2,5 };
	int iTemp = solution(n,vTemp);

	return 0;
}

남의 풀이임.
이 문제 논리
1. 제일 작은 금액으로 만들 수 있는만큼 일단 만든다 i++가 아니라 i+=money[0]으로 올라간다.
2. dp[n]을 만드는데 이 값은, 작은 금액으로 덮어씌운다.

for (int i = 1; i < money.size(); i++)//쓰고 싶은 돈
	{
		for (int j = 0; j <= n; j++)
		{
			if (j >= money[i])//어차피 이 금액보다 작은놈은 못쓰니까 처리~
				dp[j] += dp[j - money[i]] % 1000000007;

i가 커지면서 dp는 계속해서 덮어 씌어진다.