[프로그래머스] Level 3. 거스름돈

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

프로그래머스

 

 

실패방법 -> DFS로 찾기 . 시간초과발생함.

#include <string>
#include <vector>
#include <algorithm>

using namespace std;

int answer =0;
void find(int n, vector<int> money){
    
    if(n<=0 ||money.size() ==0) return;
    
    int price = money[0];
    int  value= n/price;
    money.erase(money.begin());
    
    if(n%price ==0) answer = (answer + 1)%1000000007; //해당재화 다사용하기~
    
    for(;value >=0; value--){ 
        int crr = value*price;
        find(n-crr,money);
    }
}


int solution(int n, vector<int> money) {
    
    sort(money.rbegin(), money.rend());
    find(n, money);
    return answer;
}

 

 

성공 => DP 로 풀기. 항상 DP는 내머리속에서 나오기가 힘들다  ㅠ 

 

#include <vector>
using namespace std;

int solution(int n, vector<int> money) {
    vector<int> dp(n + 1, 0);
    dp[0] = 1; // 0원을 만드는 방법은 1가지

    for (int coin : money) { // 각 동전에 대해
        for (int i = coin; i <= n; i++) { // 금액을 만들면서
            dp[i] = (dp[i] + dp[i - coin]) % 1000000007; 
        }
    }

    return dp[n]; // 최종적으로 n원을 만드는 방법의 수 반환
}