[프로그래머스] 거스름돈

문제 요약

(n을 만드는 중복 조합(길이 상관 ㄴㄴ) 개수 문제)
n원을 거슬러 준다고 할 때 화폐의 조합의 가짓수를 구하세요.
사용 가능한 화폐의 종류는 주어지며 한 화폐를 무한히 쓸 수 있다.

아이디어

사실 몰라서 구글링을 했다...
2차원 DP로 풀 수 있었다.

행 = 사용한 돈의 종류
열 = 금액
예) dp[i][j] = 0..i번째 화폐 종류를 사용해서 j 원을 만드는 가지수

이라고 했을 때 dp[돈의종류][금액+1] 배열을 만든다.
점화식은

dp[i][j] = dp[i-1][j]+dp[i]j-money[i]]
(단, i-1>=0 && j-money[i] >=0)

외울 것

n을 만드는 중복 조합 개수 문제는 2차원 DP로!
n을 만드는 중복 순열 개수 문제는 1차원 DP로!

완전탐색에는 DFS가 있다.

코드

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

int solution(int n, vector<int> money) {
    int answer = 0;
    int MOD =  1000000007;
    int** dp= new int* [money.size()];//dp[money.size][n+1]
    for(int i = 0;i<money.size();i++){
        dp[i] = new int[n+1];
        dp[i][0]=1;
        for(int j =1;j<n+1;j++){
            dp[i][j] = 0;
        }
    }
    //첫번째 줄 초기화
    for(int first = money[0];first<=n;first+=money[0]){
        dp[0][first] = 1;
    }
    //dp 테이블 채우기
    for(int i = 1;i<money.size();i++){
        for(int j = 1;j<=n;j++){
            dp[i][j] = dp[i-1][j];
            if(j-money[i]>=0){
                dp[i][j]+=dp[i][j-money[i]];
            }
            dp[i][j] %=MOD;
        }
    }
    
    answer = dp[money.size()-1][n];
    return answer;
}