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

문제 풀이 과정

LV3이고 내가 가장 못하는 DP라서 이해하는데 좀 오래 걸렸다..
완전 탐색은 금액이 100,000까지 가능해서 시간 초과가 발생할 것이다.

dp[i][j] == i개의 화폐 단위를 사용했을 때 j원을 만들 수 있는 경우의 수라고 하자

문제 예시를 먼저 직접 표로 그려보면, 위와 같이 나온다.
예를 들어 dp[2][6]일 경우 총 4가지 경우가 나온다.
1 1 1 1 1 1
1 1 1 1 2
1 1 2 2
2 2 2

위의 표로 점화식을 구할 수 있다.

dp[2][1]일 경우 1원과 2원의 조합으로 1원을 만들어야한다. 사실상 2원은 사용하지 못하기 때문에 이전 값인 dp[1][1]이 그대로 온다. 따라서 표의 그림처럼 j<money[i-1]인 요소는 이전 행의 값이 그대로 내려온다고 보면 된다.
여기서 i-1인 이유는 dp배열의 인덱스가 0부터 시작하기 때문이다.

• j<money[i-1], dp[i][j] = dp[i-1][j]

j>=i인 경우부터는 경우의 수를 합해서 구해줘야한다. dp이므로 이전 값을 이용하는 것이 핵심이다. 이전 화폐 단위의 경우의 수 + 현재 새로 추가된 화폐 단위로 거스를 때 경우의 수라고 생각하면 된다.

• j>=money[i-1], dp[i][j] = dp[i-1][j] + dp[i][j-money[i-1]]

dp[j-money[i]] : j에서 현재 동전 money[i]의 금액을 뺀 후 남은 금액을 만들 수 있는 경우의 수, 즉 현재 화폐 단위를 사용했을 때의 경우의 수

이 부분이 이해가 잘 안 됐다. 다음 예시로 이해할 수 있었다.

dp[2][6]일 경우 dp[1][6] + dp[2][4]가 된다. dp[2][4]는
1 1 1 1
1 1 2
2 2

여기에 각각 2씩 더해주면
1 1 1 1 2
1 1 2 2
2 2 2 가 되므로 새로운 화폐 단위 2를 사용했을 때의 경우의 수가 탄생한다.

이렇게 2차원 배열을 사용하게 되면 반복문으로 각 행마다 0번째 열부터 시작해서 모든 인덱스를 돌아야한다. 왜냐하면 j<money[i-1]일 때까지 dp[i][j]에 dp[i-1][j]값을 채워야하기 때문이다. 더 효율적인 방법이 없을까?

위의 그림을 다시 보면 결국 위의 값을 아래에 그대로 내려쓰는 형태가 보인다. 2차원 배열이 아닌 1차원 배열로 압축시키는 것이다.

• dp[j] = dp[j] + dp[j-money[i-1]]

class Solution {

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

      for(int i=0; i<n+1; i++){
            if(i%money[0]==0)
                dp[i]=1;
        }

먼저 첫번째 화폐 단위만을 사용하여 초기화해준다. 어차피 화폐 단위가 1개만 있기 때문에 i원을 만들기 위해서는 나눠 떨어질만큼 돈이 필요하다. 나머지가 0이 아니면 i원을 만들 수 없다. (3원을 2원만으로는 거슬러 줄 수 없다.)

for(int i=1; i<money.length; i++){
           for(int j=money[i]; j<=n; j++)
               dp[j]+=dp[j-money[i]];
 }

2차원 배열을 사용할 때와 달리 1차원 배열을 사용하면 이미 j<money[i]일 때 이전 dp값이 저장돼있다. 따라서 조건문은 j=money[i]부터 시작한다. 현재 추가된 화폐 단위를 사용하지 않고 j원을 만드는 경우의 수는 dp[j]에 저장돼있다. 여기에 새로 추가된 화폐 단위를 사용할 경우만 더해주면 된다. 위와 마찬가지로 dp[j-money[i]]가 그 값이다.