프로그래머스/동적계획법

거스름돈

연구하는개발자 2021. 2. 23. 00:01
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;
}