The Coin Change Problem

출처 : 해커 랭크

난이도 : 중간

알고리즘 : DP

 

금액과 사용 가능한 동전의 종류가 주어졌을 때, 금액을 몇 가지 방법으로 바꿀 수 있는지 계산해 보세요. 각 동전 종류는 무한대로 공급됩니다.

예
n = 3

c = [8, 3, 1, 2]

있다변화를 만드는 방법 n = 3: {1,1,1},{1.2} 그리고{3}.

기능 설명

아래 편집기에서 getWays 함수를 완성하세요 .

getWays에는 다음과 같은 매개변수가 있습니다.

• int n: 잔돈을 만들 금액
• int c[m]: 사용 가능한 동전 종류

보고

• int: 변경을 만드는 방법의 수

입력 형식

첫 번째 줄에는 공백으로 구분된 두 개의 정수가 포함됩니다.그리고, 어디:
n 변경할 금액입니다
m 동전 종류의 수입니다.
두 번째 줄에는 다음이 포함됩니다.각 동전 유형의 값을 설명하는 공백으로 구분된 정수입니다.

제약 조건

• 1 ≤ c[i] ≤50
• 1 ≤ n ≤ 250
• 1 ≤ m ≤50
• 각 c[i]고유함이 보장됩니다.

힌트

동적 프로그래밍 (DP) 을 사용하여 겹치는 부분 문제를 해결하세요
. 이 문제는 재귀적으로 해결할 수 있지만, 겹치는 부분 문제를 제거하기 위한 최적화 없이는 모든 테스트 케이스를 통과할 수 없습니다 . 같은 부분 문제를 여러 번 풀지 않도록 이전에 계산된 해를 저장하고 참조하는 방법을 생각해 보세요. * 다음과 같은 퇴화 사례를 고려하세요.
- 몇 가지 방법으로 변경할 수 있나요? 0센트? - 잔돈을 만들 수 있는 방법은 몇 가지가 있나요? > 0 코인이 없으면 센트인가요? * 솔루션 스토어를 정의하는 데 문제가 있는 경우 기본 케이스를 기준으로 생각해 보세요.(n=0). - 답변은 다음보다 클 수 있습니다. 32-비트 정수.

샘플 입력 0

4 3 
1 2 3

샘플 출력 0

4

설명 0

변화를 만드는 방법은 네 가지가 있습니다.값이 주어진 동전을 사용하여 C = [1, 2, 3] :

1. {1, 1, 1, 1}
2. {1, 1, 2}
3. {2, 2}
4. {1, 3}

샘플 입력 1

10 4 
2 5 3 6

샘플 출력 1

5

설명 1

변화를 만드는 방법은 5가지가 있습니다.n = 10값이 주어진 동전을 사용하는 단위 C = [2, 5, 3, 6]:

1. {2, 2, 2, 2, 2}
2. {2, 2, 3, 3,}
3. {2, 2, 6}
4. {2, 3, 5}
5. {5, 5}

----------------------------------------------------------------------------------------------------------------------------

 

문제 해독

주어진 동전들을 활용하여 목표 금액을 만들수 있는 조합식의 개수를 구하는 문제

 

문제접근

 

목표 금액 만큼 배열을 만든 다음 각 금액을 만들 수 있는 조합을 주어진 동전을 하나씩 사용하여 구한다음 목표금액의 조합 수를 추출

 

public static long getWays(int n, List<long> c)
    {
        long[] dp = new long[n + 1];
        dp[0] = 1;
    
        foreach(long coin in c)
        {
            for(int amount = (int)coin; amount <= n; amount++)
            {
                dp[amount] += dp[amount - coin];
            }
        }
    
        return dp[n];
    }