[프로그래머스] 거스름돈 (JAVA)

문제 출처 - Programmers

문제는 여기

코딩테스트 연습 - 거스름돈

---

[풀이]

1. 0원을 거슬러 주는 방법은 1개이니까 1을 넣어준다.

2. 모든 화폐에 맞춰서 처리를 해줘야 하므로 money만큼 반복한다.

3. 현재 화폐를 사용하기 전의 개수에서 지금 화폐를 사용하는 개수를 더해준다.

4. 제한사항에 맞춰서 나눠준다.

5. 결과를 출력한다.

[접근]

1. 거스름돈 문제라서 바로 dp나 그리디로 문제를 해결하면 되겠다고 생각하였다.

2. dp를 사용해서 문제를 해결하기로 했다.

[코드]

class Solution {
    public int solution(int n, int[] money) {
        int[] answer = new int[100001];
        // 0원을 거슬러주는 방법은 1
        answer[0] = 1;
        
        // 모든 money에 대응해서 처리
        for(int i = 0; i < money.length ; i++) {
            // 현재 화폐 ~ 다음 화폐까지 가능한 수 체크
            for(int j = money[i]; j <= n; j++) {
                // 현재 화폐를 사용하지 않고 지금화폐를 사용할 때의 개수
                answer[j] += answer[j - money[i]];
                // 제한사항에 맞게 나눠주기
                answer[j] %= 1000000007;
            }
        }
        
        return answer[n];
    }
}