728x90
programmers.co.kr/learn/courses/30/lessons/12907
코딩테스트 연습 - 거스름돈
Finn은 편의점에서 야간 아르바이트를 하고 있습니다. 야간에 손님이 너무 없어 심심한 Finn은 손님들께 거스름돈을 n 원을 줄 때 방법의 경우의 수를 구하기로 하였습니다. 예를 들어서 손님께 5
programmers.co.kr
#include <string>
#include <vector>
using namespace std;
long long d[111111];
int solution(int n, vector<int> money) {
int answer = 0;
d[0] = 1; //<1>
for (int i=money[0] ; i<=n ; i+=money[0]) //<2>
d[i] = 1;
for (int j=1 ; j<money.size() ; j++)
for (int i=0 ; i<=n ; i++)
if (i >= money[j])
d[i] += d[i-money[j]] % 1000000007; //<3>
answer = d[n];
return answer;
}