The Coin Change Problem

사이트: HackerRank
난이도: 미디움
분류: Dynamic programming

문제

어떤 숫자 n(number)과 교환가능한 코인들 c(number-array)가 주어졌을 때, n으로 교환 가능한 코인들의 경우의 수를 반환하라.

동적 프로그래밍 문제이다. 우선 작은 문제들을 설정해야하는데, 생각보다 작은 문제를 선정하는 것에 감이 잡히지 않았다. 다른사람들이 설명해 놓은 문제 풀이를 참고 해서 풀었지만, 비슷한 유형의 문제들을 많이 풀어서 익숙해져야겠다.

1. 나의 풀이

어려웠던 점

DP 알고리즘 같은 경우 대부분 메모이제이션으로 해결하게 되는데, 이 때 메모이제이션할 작은 문제들을 설정하는 것이 중요하다. 처음에 작은 문제로 설정하려고 했던 것이 아래와 같았다.

n: 1 = 0
n: 2 = (1, 1)
n: 3 = (1, 1, 1), (2, 1)
n: 4 = (1, 1, 1, 1), (2, 1, 1), (2, 2), (3, 1)
// ...

숫자 n 마다 경우의 수를 기록하면서 다음 n일 경우 조합 가능한 n의 경우의 수를 단순히 더하면 될 것이라고 생각했다. 예를들어,

n: 4 = ([n: 1] + [n + 3]) + ([n: 2] + [n: 2]);
       	1 + (1 + 1 + 1)  	// 1 + 3
       	1 + (2 + 1)			// 1 + 3
		1 + 3				// 1 + 3
       	(1 + 1) + (1 + 1)	// 2 + 2(중복)
       	2 + (1 + 1)			// 2 + 2(중복)
       	2 + 2				// 2 + 2
// n: 4는 총 4가지의 경우의 수를 가진다.

이렇게 할 경우 중복이 되는 경우의 수가 생기기 때문에 중복 제거라는 복잡한 작업이 필요하다. 위와 같이 생각하다가 작은 문제를 잘못 설정했다는 생각이 들어서 다른 사람들의 문제 풀이를 찾게 되었다.

2. 다른사람의 풀이

function getWays(n, c) {
    // 1 ~ n까지의 경우의 수를 기록할 변수를 설정한다.
    const ways  = new Array(n + 1).fill(0);
    // index가 0일 경우 자기 자신이기 때문에 1로 설정한다.
    ways[0] = 1;

    // 주어진 코인을 순회하면서 경우의 수를 채워나간다.
	// 각 코인마다 1~n까지를 순회하기 때문에 정렬도 필요없다.
    c.forEach(coin => {
        for (let i = 1; i < ways.length; i++) {
            // 코인 값보다 현재 순회하는 숫자(i)가 클 경우
            // 코인 값이 현재 숫자(i)를 구성하는 원소가 될 수 있다는 뜻이다.
            if (coin <= i) {
                // 현재 코인 값을 뺀 나머지의 경우의 수를 가져와 더해준다.
                ways[i] += ways[i - coin];
            }
        }
    });
    
    return ways[n];
}

내가 간과 했던 것이 주어진 코인들의 교환 가능한 경우의 수라는 것이었다. 결국 코인들을 기준으로 작은 문제를 설정하는 것이 포인트였던 것이다.

결론

작은 문제는 coin들의 조합의 경우의 수이다.