Lv 3. 거스름돈

 

https://school.programmers.co.kr/learn/courses/30/lessons/12907

프로그래머스

 

 

 

이 문제는 거스름돈을 주는 방법의 가짓수를 계산하는 문제다.
주어진 동전 종류와 목표 금액 n 대해,
각각의 동전을 사용해 목표 금액을 만들 수 있는 방법의 수를
동적 계획법(DP)을 활용하여 계산하면 풀기 쉽다.

dp 배열에는 금액별로 거스름돈을 만들 수 있는 경우의 수를 저장한다.
배열의 크기는 n+1로 초기화되며,
dp[i]는 금액 i를 만들 수 있는 경우의 수를 나타낸다.

먼저 가장 작은 동전에 대해 처리하며,
해당 동전으로 나누어떨어지는 금액은 초기값으로 1로 설정한다.
이후 나머지 동전들을 순차적으로 처리하며,
현재 동전을 포함하여 금액을 만들 수 있는 경우의 수를 갱신한다.
갱신은 dp[j]+=dp[j−money[i]] 식을 통해 이루어지며,

이는 현재 동전을 사용해 금액 j를 만들 수 있는 경우의 수를 기존 경우의 수에 더하는 방식이다.
마지막으로,
dp[n] 값을 1000000007로 나눈 나머지를 반환하여 최종 결과를 출력한다.

 

 

package Programmers;

import java.util.Arrays;

class p거스름돈 {

	public int solution(int n, int[] money) {
		Arrays.sort(money);

		long[] dp = new long[n+1];

		for(int i =0; i<=n ;i++){
			if(i % money[0] == 0)
				dp[i]=1;
		}

		for(int i=1; i<money.length ; i++){
			for(int j=money[i]; j<=n; j++){
				dp[j] += dp[j-money[i]];
			}
		}

		return (int)(dp[n] % 1000000007);
	}
}