문제링크

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

구현방법

화폐의 종류가 있다.

n -> 돌려줘야할 거스름돈의 합.

DP로 보임.

내가 1원 2원 5원

4원을 거슬러준다.

1 4개

1 2개 2 1개

2 2개

1 2 3 4 5 6 7 8

1 2 2 3

탐색 문제

중복은 허용하지만 가지수에서 중복은 허용하지않음.

가지수가 1억이 넘어간다? -> 탐색으로 돌경우 시간 초과 발생확률이 높지않나?

화폐단위 100종류 이하?

1 1 1 1 1

1 1 1 2

1 2 2

5

2 1 1 1 이나오면안됨. idx 기준으로 뽑기?

cost -> n 원

n== cost 가 같은 경우

answer+=1;

return;

n을 초과하는 경우

return;

DFS를 통해서 진행하는 경우 -> 효율성체크에서 시간초과 발생

힌트 사용 : DP알고리즘 규칙을 봤습니다.

https://dev-note-97.tistory.com/242

후기 : DP 알고리즘 문제는 볼때마다 결과를 도출하는게 엄청 어렵다고 느껴지네요. 동적계획법 문제도 좀 풀 수 있게 같은 알고리즘 다른 문제를 꽤 많이 풀어봐야 할 거같습니다.

탐색을 통해서 풀리겠다 했는데 효율성을 간과해서 시간초과가 발생했습니다.

구현알고리즘

DP

CODE

처음 DFS 를 사용한 코드 -> 효율성 시간 초과발생 (실패)

class Solution {

    boolean visited[];

    int result = 0;

    int[] moneys;


    public int solution(int n, int[] money) {
        moneys = money;


        visited = new boolean[money.length];

        start(0,0,n);
        return result;
    }

    private void start(int cost,int index,int end) {
        if(cost == end){
            result += 1;
            return;
        }
        else if(cost > end){
            return;
        }
        for(int idx =index; idx <moneys.length;idx++){
                start(cost+moneys[idx],idx,end);
        }


    }
}

DP 알고리즘

/**
 * 알고리즘 : DP 알고리즘.
 */
class Solution {
    public int solution(int n, int[] money) {
        int dp[][] = new int[money.length+1][n+1];

        for(int idx = 1; idx < money.length+1;idx++){
            for(int next = 0; next <n+1;next++){
                if(next == 0){
                    dp[idx][next] = 1;
                }
                else{
                    //현재 잔돈보다 작은 경우 -> 이전 값을 가져온다.
                    if(next < money[idx-1]){
                        dp[idx][next] = dp[idx-1][next];
                    }
                    //현재 잔돈 보다 큰경우 점화식 계산 dp[i][j] = dp[i-1][j] + dp[i][j - money[idx]]
                    else{
                        dp[idx][next] = (dp[idx-1][next] + dp[idx][next - money[idx-1]]) % 1000000007;
                    }
                }
            }
        }

        return dp[money.length][n];
    }
}