프로그래머스 12907 거스름돈 자바 풀이

난이도 : Lv. 3

풀이일 : 2412275

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

프로그래머스

---

문제

---

아이디어

• 각 동전에 대해 해당 동전의 가격부터 궁금한 금액까지 해당 동전으로 만들 수 있는 개수 추가

---

코드

class Solution {
    public int solution(int n, int[] money) {
        int answer = 0;
        int[] dp = new int[n + 1];
        dp[0] = 1;
        
        for (int coin : money) {
            for (int i = coin; i < n + 1; i++) {
                dp[i] += dp[i - coin];
            }
        }
        answer = (int) dp[n] % 1000000007;
        
        return answer;
    }
}

• dp 배열은 구해야할 수까지 생성하기 위해 n+1
• 0원을 만들 수 있는 경우의 수 1 기록
• 각 동전에 대해 반복하며 해당 동전부터 n값까지 동전을 사용해 만들 수 있는 개수 기록
• 답이 너무 커질 경우 처리를 위해 문제 요구사항 수로 나누어 answer 기록 및 반환

---

제출 결과