개요

[HackerRank] TheCoinChangeProblem

Given an amount and the denominations of coins available, determine how many ways change can be made for amount. There is a limitless supply of each coin type.

접근방식

1. 다이나믹 프로그래밍을 통한 접근이다.

2. 2차원 벡터를 선언 후, 행에는 현재 남은 금액, 열에는 c에서 몇 번째 동전을 사용할 건지를
   넣어주었다.

3. long long Get(int target, int index, vector<long>c, vector<vector<long long>>& dp)

   각 함수에서 target은 남은 금액, index는 벡터c에서 몇 번째 동전을 사용할 것인지를 뜻한다.
   take변수와 notake변수로 나뉘어 있다.
   take는 현재 동전을 챙겼을 때, notake는 현재 동전을 안 챙겼을 경우이다.

4. • 동전을 챙겼을 경우, target값만 해당 동전값만큼 빼준 후, index는 건드리지 말고 다음 재귀로 넘어간다.
     이유는 각 재귀당 동전 하나를 챙기도록 구현했으므로
     다음 재귀에서도 똑같은 동전을 또 챙길 수 있기 때문이다.

   • 동전을 안 챙겼을 경우, 해당 index의 동전은 더 이상 안 챙긴다고 가정하고
     target값은 변함없고, index만 낮춰 다른 동전에 대해 처리하도록 재귀를 구현했다.

전체 코드

/*
 * Complete the 'getWays' function below.
 *
 * The function is expected to return a LONG_INTEGER.
 * The function accepts following parameters:
 *  1. INTEGER n
 *  2. LONG_INTEGER_ARRAY c
 */

long long Get(int target, int index, vector<long>c, vector<vector<long long>>& dp){
    if(index ==0) return target % c[0] == 0;
    if(dp[index][target]!=0) return dp[index][target];
    
    long long take = 0;
    long long noTake= Get(target,index-1,c,dp);
    
    if(c[index] <= target){
        take = Get(target - c[index] , index , c, dp);
    }
    
    
    return dp[index][target] = take + noTake;
    
}

long getWays(int n, vector<long> c) {
    int size = c.size();
    vector<vector<long long>> dp(size, vector<long long>(n+1,0));
    return Get(n, size-1,c,dp);
}

생각

동적계획법 문제를 좀 더 풀어보며 익혀봐야겠다. 아직 풀이가 바로 안 떠오른다..