[c++] Coin Combinations(동전 조합 알고리즘, 순서 고려 X) with Dynamic Programming

이번엔 dynamic programming을 이용해서

동전 조합 알고리즘 문제를

해결하는 법을 정리해보려고 한다

 

동전 조합, 즉 Coin Combinations은

우리가 학창시절 수학과목에서 볼 수 있었던

확률과 통계 유형의 문제인데

각 동전이 주어지고 합계가 주어질 때

합계를 만들 수 있는 경우의 수를 구하는 문제이다

 

이같은 문제는 동전의 순서를 고려하는 경우와

동전의 순서를 고려하지 않는 경우로 구분할 수 있는데

이번 문제는 동전의 순서를 고려하지 않는 경우였다

(조금 더 간단하게 구현이 가능하다)

 

알고리즘 문제는 다음과 같다

 

 

 

그리고 Input, Output, Constraints는 다음과 같다

 

 

이러한 Coin Combinations 문제는

대표적인 dynamic programming 문제이다

 

dynamic programming (동적 프로그래밍)의 수업 내용 정리는

아래 링크를 참고

https://think0905.tistory.com/entry/computer-science-Dynamic-Programming-%EB%8F%99%EC%A0%81-%ED%94%84%EB%A1%9C%EA%B7%B8%EB%9E%98%EB%B0%8D

[computer science] Dynamic Programming (동적 프로그래밍)

 

---

 

Coin Combinations를 dp로 해결하는

기본 idea는 다음과 같다

 

위 Example처럼

합계 7을 만들기위해 1, 2, 3이 있다고 하면

dp의 기본 idea는

2를 한 개만 사용해서 합계 7을 만들려고하면

합계 7-2=5를 만드는 방법의 수만 구해주면 된다는 것이다

그럼 합계 5를 만드는 모든 방법에 2만 추가해주면 되기 때문이다

 

따라서 1부터 sum까지 for loop을 돌면서

모든 coin에 대해서

합계에서 coin을 뺀 만큼의 경우의 수를 저장해준다

 

그럼 bottom-up 방식으로 합계 1을 생성하는 경우의 수부터

차근차근 각 경우의 수가 구해질 것이고

이를 이용해서 input으로 들어온 합계를 만드는 경우의 수를 구하는 것이다

 

 

base case를 정의해줘야하는데

합계 0을 만들기 위해서는 아무 동전을 사용하지 않는

1가지 방법이 있으므로

 

각 합계별 경우의 수를 저장하는 vector를 선언한 뒤

0을 1로 초기화해준다

vector<long> dp(sum+1, 0);
dp[0] = 1;

 

 

그런 다음 1부터 sum까지 loop을 돌면서

각 coin 별로 합계를 만드는 경우의 수를 구해서

vector에 저장해준다

 

for (int i = 1; i  <= sum; i++) {
    for (int coin : coins) {
        if (i >= coin) {
            dp[i] = (dp[i] + dp[i - coin]) % INT_MAX;
        }
    }
}

 

INT_MAX로 나눠준 이유는

문제 요구사항에 큰 값을 다루기 위해

INT_MAX로 나눈 나머지 값을

반환하라고 명시되어있기 때문이다

 

 

그런 다음 input으로 들어온 sum번째 index에

저장된 vector값을 반환해주면 된다

 

 

전체 코드는 아래와 같다

#include <iostream>
#include <vector>
#include <algorithm>
#include <climits>

#include "functions.hpp"

using namespace std;

long coinCombinations(int n, int sum, vector<int>& coins)
{
    vector<long> dp(sum+1, 0);
    dp[0] = 1;
    for (int i = 1; i  <= sum; i++) {
        for (int coin : coins) {
            if (i >= coin) {
                dp[i] = (dp[i] + dp[i - coin]) % INT_MAX;
            }
        }
    }
    return dp[sum];
}

 

 

dp는 코드 구현 자체는 늘 간단한데

idea를 생각하는데에 시간을 많이 잡아먹는 것 같다

많은 훈련이 필요한 알고리즘인 것 같다