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

프로그래머스

코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요.

programmers.co.kr

풀이

동적계획법을 사용해서 해결했다. 해당 문제는 2차원으로 생각해보면 규칙이 보인다. n = 5, money = [1, 2, 5] 인 경우를 살펴보자.
가로 줄은 금액, 세로 줄은 동전의 종류이다.

위의 표를 dp[][]라고 하고 가로줄을 j, 세로줄을 i, 새로 추가되는 동전의 금액을 w라고 했을 때, 위의 표를 보면 w == j 가 되는 순간부터 값이 달라지는 것을 알 수 있다. 조금 더 자세히 살펴보면 w == j일 때는 dp[i][j] = dp[i-1][j] + 1이 되고, w < j 일 때는 dp[i][j] = dp[i-1][j] + dp[i][j-w] 임을 알 수 있다. 따라서 이 규칙을 그대로 구현해주면 된다.

코드

C++

#include <string>
#include <vector>
#include <algorithm>
#define DIV 1000000007
using namespace std;

int dp[101][100001];

int solution(int n, vector<int> money) {
    sort(money.begin(), money.end());

    for (int j = 0; j <= n; j++) {
        int coin = money[0];
        if (j % coin == 0) 
            dp[1][j] = 1;
    }

    for (int i = 1; i <= money.size(); i++) {
        int coin = money[i];
        for (int j = 0; j <= n; j++) {
            if (j < coin) dp[i + 1][j] = dp[i][j];
            else dp[i + 1][j] = (dp[i][j] + dp[i + 1][j - coin]) % DIV;
        }
    }
    return dp[money.size()][n];
}

Java

import java.util.Arrays;

class Solution {
    static int DIV = 1000000007;
    int dp[][];

    public int solution(int n, int[] money) {
        dp = new int[money.length + 1][n + 1];
        Arrays.sort(money);
        for (int j = 0; j <= n; j++) {
            int coin = money[0];
            if (j % coin == 0)
                dp[1][j] = 1;
        }
        for (int i = 1; i < money.length; i++) {
            int coin = money[i];
            for (int j = 0; j <= n; j++) {
                if (j < coin) dp[i + 1][j] = dp[i][j];
                else dp[i + 1][j] = (dp[i][j] + dp[i + 1][j - coin]) % DIV;
            }
        }
        return dp[money.length][n];
    }
}