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

프로그래머스

---

의식의 흐름

dp 문제네

-> 0원~n원까지 가능한 경우의 수를 다 저장하면 되겠다.

-> 풀고 나니 1,000,000,007로 나눈 나머지라는 조건을 까먹고 그냥 원래 값을 return했는데 통과네..?

-> 1,000,000,0007로 나누는 코드 추가해서 제출했는데 시간 초과 🙄

-> 코드 살짝 수정하고 통과

문제 자체는 어렵지 않았는데 이 문제 덕분에 내가 쓰던 로직을 살짝 수정해서 좀 더 빠른 로직으로 수정할 수 있었다

풀이 과정

1. i번째 동전까지 사용해서 j원 만들 수 있는 경우의 수를 담을 배열(dp)을 만든다.

2. i번째 동전에 대해 dp[i][j]를 구한다.

2-1) 0원을 만들 수 있는 경우의 수는 무조건 1

2-2) dp[i][j] = dp[i-1][j];

2-3) 만약 i번째 동전(money[i-1])이 j원보다 작거나 같은 경우, dp[i][j] = dp[i-1][j] + dp[i][j-money[i-1]];

원래 코드는 2-2를 2-3에 대한 else문으로 뒀었는데 이렇게 두니까 시간초과가 나더라ㅏ,,

2-4) dp[i][j]를 1,000,000,007로 나눈 나머지로 바꿔준다.3. dp[moneyCnt][n]을 return한다.

 

코드

import java.util.*;

class Solution {
    public int solution(int n, int[] money) {
        int moneyCnt = money.length;
        int[][] dp = new int[moneyCnt+1][n+1];
        
        for(int i=1;i<=moneyCnt;i++){
            dp[i][0] = 1;
            for(int j=1;j<=n;j++){
                dp[i][j] = dp[i-1][j];
                if (money[i-1] <= j){
                    dp[i][j] = dp[i-1][j] + dp[i][j-money[i-1]];
                }
                
                dp[i][j] %= 1_000_000_007;
            }
        }
        
        return dp[moneyCnt][n];
    }
}