동전 교환 알고리즘: 주어진 화폐로 특정 금액 만드는 경우의 수 구하기

동전 교환 알고리즘 문제 : 경우의 수 구하기

동전 교환 알고리즘 문제는 다이나믹 프로그래밍 영역에서 다양한 바리에이션으로 출제되는 문제입니다(저도 몰랐어요. 이번에 DP 공부하면서 알게되었습니다. 코린이라서...).
아래에 해설할 문제는 '몇 종류의 화폐가 주어지고, 이 화폐들을 조합해서 특정 금액을 만들 수 있는 경우의 수'를 구하는 유형의 문제입니다.
해설을 보시고 DP에 익숙해져서 또 다른 동전 교환 알고리즘 문제와 DP 문제들도 쉽게 풀 수 있게 되면 좋겠습니다!

해설 영상

---

영상이 좀 많이 길어요. 왜냐면 제가 겨우겨우 이해를 했기 때문에... 저와 같이 이해가 느리신 분이 계시면 도움이 되시라고 최대한 자세하게, 반복하면서 설명을 해서 그렇습니다. 중간 중간 멈춰가면서 생각해보시면 이해가 되실 거라고... 생각해요!

구현 코드

---

먼저 코드를 짜보시고, 어려우시면 참고해 보시길 권장드려요

public long coinExchange(int target, int[] type) {
    /*
    *  target : 구해야 하는 최종 금액
    *  bottomup[][] : 경우의 수 계산 결과를 담아놓는 배열
    *  i : 현재 비교하려는 화폐의 순번
    *  type[i] : 현재 비교하려는 화폐
    *  j : 현재 경우의 수를 구하려는 금액
    */
    Arrays.sort(type); // 위의 해설에서는 빠졌지만, 화폐 순서도 뒤죽박죽일 수 있으니까 오름차순으로 정렬해둬야 해요

    long[][] bottomup = new long[type.length][target + 1];

    for (int i = 0; i < type.length ; i++) {
        for (int j = 0; j <= target; j++) {
            if (j == 0) { // 구하려는 금액이 0원인 경우
                bottomup[i][j] = 1L;
            }
            else if (i == 0) { // 현재 비교하려는 화폐가 첫번째 화폐인 경우
                if (j % type[i] == 0) {
                    bottomup[i][j] = 1L;
                } // else -> 0(default)
            }
            else if (j < type[i]) { // 현재 경우의 수를 구하려는 화폐 액면가보다, 만들려는 금액이 작은 경우
                bottomup[i][j] = bottomup[i - 1][j];
            }
            else { // 경우의 수를 구할 수 있는 일반적인 경우
                bottomup[i][j] = bottomup[i - 1][j] + bottomup[i][j - type[i]];
            }
        }
    }

    return bottomup[type.length - 1][target];
}