4 ★★★ 프로그래머스 - 거스름돈 (DP)

220605

어렵ㅠ

 

220317

dp[i]를 dp[m]으로 바꾸는게 훨씬 보기 편할 수도.. 차라리 dp[money] 풀네임 쓰거나 i, j로 쓰면 헷갈릴 수가 있음

import java.util.*;
 
class Solution {
    public int solution(int n, int[] moneys) {
        Arrays.sort(moneys);
        int[] dp = new int[n+1];
        dp[0] = 1;
        for(int money=1; money<=n; money++){
            dp[money] = (money%moneys[0]==0)? 1:0;
        }
        
        for(int j=1; j<moneys.length; j++){
            for(int money=moneys[j]; money<=n; money++){
                dp[money] = (dp[money] + dp[money-moneys[j]])%1000000007;    
            }
        }
 
        return dp[n];
    }
}

 

220312

또 푸는데 더럽게 어려웠다..

이건 dp에 도를 터고 있어야 풀리는 문제인듯

코드는 진짜 짧은데 저 점화식이 왜 저렇게 탄생됐는지

그리고 매우 의아했던 dp[0]=1인지..

당연히 0원을 만들 수 있는 경우의 수는 없는데 왜 1을 넣어야 코드가 돌아가는지..

결론만 말하면 dp[0]=1은 점화식을 충족시키기 위해 값을 끌어오는거임 dp[1]~dp[n]까지는 1원부터 n원까지 만들 수 있는 경우의 수가 맞는데 dp[0] 혼자 아니라는 얘기임 1차원1배열로 만들기 위해 끌어다 쓴거임

 

점화식 탄생은 2번째링크보고 본문보니까 이해됨..

dp[0]=1인 이유, dp를 2차원배열에서 1차원배열로

만들 수 있는 이유(이건 누적을 이용해서 차원하나를 지워버린거임)..

 

걍 점화식만 띡 보고 이해 절대 불가능함(내 수준 기준으로)

 

 

 

혼자서 끙끙 앓다가 해설 보고 풀었음. 

 

문제에서 점화식을 정의할 수 있는 테이블을 만들어야하는데 

 

나같은 경우는 쓸데없이 1부터 n까지의 금액을 만들 수 있는 동전조합의 경우를 전부 써서 만들어봤는데 

 

그런 식으로 해서는 절대로 규칙을 못찾고 , 

 

일정한 규칙을 이루는 table을 찾아야하는데 (점화식을 찾기 위해서)

행은 동전의 단위 개수(오름차순 순으로 1개,2개,3개 이렇게) 

열은 1부터 n까지의 금액 total값으로 해줘야 규칙을 찾을 수 있음.

 

 

 

/*

ex)문제에서 주어진 예시의 돈의 종류인 1,2,5와 거슬러 주어야하는 금액이 5일 때,

// i는 동전 단위의 조합 수. j는 거슬러주어야하는 금액 

    

즉 

i=0  --> 1원 1개만 사용 가능한 경우

i=1  --> 1,2원 2개 사용 가능한 경우

i=2  --> 1,2,5원 3개 사용 가능한 경우

 

 

dp[1][5] -> 1,2원 2종류의 동전들을 사용하여 5원을 거슬러줄 수 있는 경우의 수

dp[0][10] -> 1원 1종류의 동전들을 사용하여 10원을 거슬러줄 수 있는 경우의 수

dp[2][30] -> 1,2,5원 3종류의 동전들을 사용하여 30원을 거슬러줄 수 있는 경우의 수

 

이렇게 구분하는 이유는 새로운 돈의 단위값이 튀어나오기 전까지는 

즉 2원만 쓰는 경우와 2,3원 두개를 쓰는 경우를 비교해볼 때

3원을 거슬러주기전까지 경우의수는 서로 같다는 것이다.

 

아

 

밑에 참조된 블로그 2개 글 정독 5번은 해서 이해한 것 같다.

 

 

int[][] dp = new int[money.length][n+1];

dp[i][j] = dp[i-1][j] + dp[i][j- (현재money단위)];*/

 

설명은 밑에 참조된 블로그 글 2개 ㄱ 글자로 쓰려니까 도저히 못하겟다

 

솔직히 해설 안보면 하루종일 풀어도 절대 못풀었을듯.. 

 

특정한 dp[i][j] 값을 만들기 위해 2가지 경우에서 끌어와야함

 

하나는 dp[i-1][j] 다른 하나는 dp[i][j-(현재 새로운money의 단위)] 

 

근데 이거 dp를 또 2차원 배열로 풀면 메모리가 부족해서 효율성에서 틀린다.

 

즉 dp[i][j]를 만들기위해 끌어야하는 값들 중 하나인 dp[i-1][j]를

 

1차원 배열인 dp[j]로 표현해주려면 기존에 저장된 dp[j]값을 그대로 활용해주면됨(이것도 이해하느라 몇십분걸림)

 

 

public int solution(int n, int[] money) {
      int answer = 0;
      int[] dp = new int[n+1];
      dp[0]=1;
      for(int j=0; j<=n; j++){
          if( j%money[0]==0 ) dp[j]=1;
      }
      
      // for(long i : dp){
      //     System.out.print(i+" ");
      // }
      // System.out.println();
      
      for(int i=1; i<money.length; i++){
          for(int j=money[i]; j<=n; j++){
              dp[j] = (dp[j] + dp[ j-money[i] ])%1000000007;
              // System.out.println(dp[j]);
          }
          // for(long k : dp){
          //     System.out.print(k+" ");
          // }
          // System.out.println();
      }
      
      
      return dp[n];
  }

 

 

참조 링크 

https://gurumee92.tistory.com/64

https://ydeer.tistory.com/59