[프로그래머스] 거스름돈

작성일: 2024-12-07

문제 링크 : https://school.programmers.co.kr/learn/courses/30/lessons/12907

접근 방식

n이 최대 10만까지 주어진다. 일반적인 조합을 사용하는 경우, 시간을 초과할 가능성이 매우 높기 때문에 DP를 이용해서 최적의 합을 구해야 한다.

메모이제이션을 이용해서, 이전에 사용했던 경우의 수를 구해와서 조건을 통해 새로운 경우의 수를 구해야 한다.

잘못된 접근

import java.util.*;

class Solution {
    public int solution(int n, int[] money) {
        int answer = 0;
        int[] num = new int[n+1]; // 돈을 만들 수 있는 가짓 수를 저장할 배열
        num[0] = 1;
        Arrays.sort(money); // 화폐 종류 정렬

        // n원을 만들 수 있는 최적의 수를 구하기, 1원부터~n원까지
        for(int i=1; i<=n; i++){
            for(int j=0; j<money.length; j++){
                // money[j]로 금액을 만들 수 있다면
                if(i-money[j] >= 0){
                    num[i] += num[i-money[j]];
                    num[i]%=1000000007;
                }
            }
        }
        return num[n];
    }

}

1부터 시작해서, n까지 최적의 수를 구하는 알고리즘이다.

디버깅을 해 보니, 중복으로 값이 계산되고 있었다.

예를 들어서, 3의 경우 (111, 12) 이렇게 두 가지만 존재해야 하지만 (111, 12, 21)과 같이 카운트되면서 세 가지가 존재하는 것으로 저장된다.

따라서 값을 중복으로 처리하지 않도록, 구조를 변경해야 했다.

잘 된 접근

현재 접근은, i부터 모든 머니로 만들 수 있는 경우의 수를 구해서 더하고 있기 때문에, 이전에 사용된 경우의 수 일지라도, 중복해서 경우의 수를 구하고 있다.

따라서, 화폐 종류 별로 한 번씩만 경우의 수를 구하도록 변경해야 한다.

이는 for문의 내부와 외부를 변경하면 해결이 되는 문제이다.

// n원을 만들 수 있는 최적의 수를 구하기, 1원부터~n원까지
for(int j=0; j<money.length; j++){
    for(int i=money[j]; i<=n; i++){
        // money[j]로 금액을 만들 수 있다면
        if(i-money[j] >= 0){
            num[i] += num[i-money[j]];
            num[i]%=1000000007;
        }
    }
}

내부와 외부를 변경해주고, i값은 money[j]부터 시작하도록 한다. (굳이 이전 값을 구할 필요가 없음. 최솟값(이전에 정렬을 했기 때문)으로 구할 수 없는 경우의 수라면 0을 그대로 리턴하면 되기 때문)

결과

소스 코드

import java.util.*;

class Solution {
    public int solution(int n, int[] money) {
        int answer = 0;
        int[] num = new int[n+1]; // 돈을 만들 수 있는 가짓 수를 저장할 배열
        num[0] = 1;
        Arrays.sort(money); // 화폐 종류 정렬

        // n원을 만들 수 있는 최적의 수를 구하기, 1원부터~n원까지
        for(int j=0; j<money.length; j++){
            for(int i=money[j]; i<=n; i++){
                // money[j]로 금액을 만들 수 있다면
                if(i-money[j] >= 0){
                    num[i] += num[i-money[j]];
                    num[i]%=1000000007;
                }
            }
        }
        return num[n];
    }

}