[C++로 풀이] 거스름돈 (DP)⭐⭐⭐

📌 거스름돈

난이도 ⭐⭐⭐

🚀 문제

🚀 내 풀이

✈ 1 차 풀이 (DFS) ⏰시간초과

#include <string>
#include <vector>
#include <algorithm>

using namespace std;

void DFS(vector<int>& money, int& answer, int n, int index) {
    if (index == money.size())
        return;

    for (int i = index; i < money.size(); ++i) {
        for (int num = 1; num <= n; num++) {
            if (n - money[i] * num < 0)
                break;
            if (n - money[i] * num == 0) {
                answer = (answer + 1) % 1000000007; 
                break; 
            }
            DFS(money, answer, n - money[i] * num, i + 1);
        }
    }
}

int solution(int n, vector<int> money) {
    int answer = 0;
    DFS(money, answer, n, 0);
    return answer;
}

• 문제에서 n의 크기는 1000 번만 반복해도 시간초과 나는 크기인 100,000 에다가.. 문제에서 정답이 아주 커질 수도 있다고 언급한만큼, 입력 크기가 상당하니 반드시 시간 복잡도를 고려하면서 풀어야 하는 문제 라는 점을 생각하면서 풀었어야 했다.
  • 재귀 안에서 이중 for문을 돌렸으니 시간초과가 나는건 당연지사..
  • 시간 복잡도 꼭꼭꼭 생각하자!!!!!

일단 이 1차 풀이의 로직은 백트래킹과 같았다. 1 ~ n 을 곱한 화폐들끼리의 조합을 모조리 시도해보고 안되면(n < money[i] * num) 되돌아가고 아직 돈 더 더할 수 있으면 DFS 깊게 들어가고 n과 일치하는 금액을 찾았다면 answer 증가!

• 1원 x 1
  • 2원 x 1
    • 5원 x 1 ❌ (1x1 + 2x1 + 5x1 > 5)
  • 2원 x 2 ⭕ (1x1 + 2x2 == 5)
• 1원 x 2
  • 2원 x 1
    • 5 원 x 1 ❌ (1x2 + 2x1 + 5x1 > 5)
  • 2원 x 2 ❌ (1x2 + 2x2 > 5)
• 1원 x 3
  • 2원 x 1 ⭕ (1x3 + 2x1 == 5)
• 1원 x 4
  • 2원 x 1 ❌ (1x4 + 2x1 > 5)
• 1원 x 5 ⭕ (1x5 == 5)

🔥 이 문제는 Dynamic Programming 으로 풀어야 함!

위 같이 백트래킹으로 풀이했다가 어떻게 시간 초과를 해결해야할지 모르겠어서 구글링을 했는데.. 생각지도 못했다. 이 문제가 DP 문제였다는 것을.. ㅠ ㅠ 어떻게 DP 문제지? 하며 동공 지진.. 그리고 다른 분들의 풀이를 보면서 DP를 사용한 풀이를 이해하는데 한참 걸렸다.. 역시 아직 많이 부족한듯 하다. DP 문제 많이 풀어봐야겠다..🤔 아무튼! 다른 분들의 풀이를 보며 공부한 후 정리하는 글이기 때문에 미리 출처를 남긴다.

• 출처 및 참고
  • 구르미님 블로그
  • 현록님 블로그

시간 복잡도 차원에서

• 우선 n의 최대 크기는 100,000 이지만 화폐 단위는 최대 100 개이기 때문에 n과 money를 이중 for문으로 매칭시키는 것 까지의 시간 복잡도는 괜찮다.(1억을 넘지 않음)
  • 시간 복잡도는 딱 이 수준을 넘지 않아야 한다.
• 입력 크기가 상당하기 때문에 다이나믹 프로그래밍으로 문제를 풀 수 있을지, 즉 점화식을 세울 수 있는 관계가 있는지를 검사해보았어야 했다.

2차원 DP 배열 👉 “점화식”에 2 가지 정보가 필요

• arr[4][11] (2,3,5,8 이렇게 4번째 화폐까지라서 4행) 👉 [2, 3, 5, 8] 원만 사용해서 n = 11원을 나타낼 수 있는 경우의 수 = 1️⃣ + 2️⃣
  • [2, 3, 5, 8] 에서 8 을 포함하지 않은 경우(a[3][11])와 8 을 포함한 경우(a[4][3])로 나눠볼 수 있겠다.
  • 1️⃣ 8 원은 아예 쓰지 않고 오로지 [2, 3, 5]원만 사용해서 11원을 나타낼 수 있는 경우의 수
  • 2️⃣ [2, 3, 5, 8] 원으로 3원을 나타낼 수 있는 경우의 수
    • 어차피 8원으론 `4`원을 만들지 못하기 때문에 사실상 [2, 3, 5]원 만으로 3원을 만드는 경우의 수와도 같다. (1️⃣만 그대로 물려받았을 것이다.)
    • 8 을 포함하여 n = 11 원을 나타내는 경우라면 [2, 3, 5]원 만으로 11 - 8 = 3 원을 만드는 모든 경우에다가 8 만 붙이면 11 이될테니까 이는 곧 [2, 3, 5]원 만으로 11 - 8 = 3 원을 만드는 경우의 수와 동일하다.
      • [2, 3, 5] 로 3을 만들 수 있는 경우는 [3] 이 있겠다. 여기에 8 만 붙는 다고 생각해보면 [3, 8] 로 11을 만들 수 있게 된다.
        • 그러니 [2, 3, 5] 로 11을 만들 수 있는 경우의 수는 곧 8 을 꼭 포함하여 [2, 3, 5]로 3을 만드는 경우의 수와 동일하다.
      • 즉 [2, 3, 5, 8] 로 11원 만들기에 8을 포함한 조합으로서 포함될 수 있는 것이다. 따라서 n - 해당 화폐 를 만든 경우의 수와 같아지는 것이다.
• [1, 2, 5] 원만 사용해서 n = 5원을 나타낼 수 있는 경우의 수 = 1️⃣ + 2️⃣
  • 1️⃣ 5 원은 아예 쓰지 않고 오로지 [1, 2]만 사용해서 5원을 나타낼 수 있는 경우의 수
  • 2️⃣ 5 원을 꼭 포함하여 [1, 2, 5]로 0원을 나타낼 수 있는 경우의 수
    • [1, 2, 5]로 0 원을 나타낼 수 있는 방법은 없다! 그러니 없는 조합에 5 만 붙여서 [5] 한가지가 이 경우에 해당 되겠다.
      • 즉, [1, 2, 5]로 0 원을 나타낼 수 있는 방법의 수는 5를 꼭 포함한 [1, 2, 5]로 5 원을 나타낼 수 있는 방법의 수와 동일하다.
        • 전자는 아무 돈도 안썼을 때(0원)의 한가지 (조합 [ ]), 후자는 이 조합해 5 을 붙인, (즉 0 + 5 = 5) (조합 [5]).
          • 둘 다 1 가지로 같다.

점화식에 필요한 정보

• ✔ 행 1️⃣ 사용할 화폐의 조합
  • ex. [1] 👉 1원만 사용, [1, 2] 👉 1,2 원만 사용, [1, 2, 5] 👉 1, 2, 5 원만 사용
    • 이렇게 3 가지로 나눌 수 있음
• ✔ 열 2️⃣ 나타낼 금액 (0,1,2, .. ,n-1,n)

점화식에 필요한 정보가 2 가지이므로 2 차원 테이블에 담아나가면 된다.

첫 행의 점화식 👉 money[0]원 화폐 하나로만 j = 0,1,..,n 을 표현할 수 있는 경우

• j 가 money[0] 의 배수일 때
  • arr[0][j] = 1
    • money[0]가 10 이라면 10의 배수들의 수는 다 10원 여러개로 표현할 수 있는 수이니 1가지
• j 가 monwy[0] 의 배수가 아닐 때
  • arr[0][j] = 0
    • money[0] 하나로 money[0] 의 배수가 아닌 수들을 표현할 순 없다.

첫 행 이외의 점화식 👉 arr[i][j] = arr[i - 1][j] + arr[i][j - money[i]]

• i 👉 i 는 0 부터 money.size() 까지

• j 👉 j 는 0 부터 n 까지

• arr[i][j] = 1️⃣ + 2️⃣
  • { money[0], money[1], .. , money[i] } 화폐들로만 j원을 표현할 수 있는 경우의 수
    • (무조건 i번째까지의 화폐를 꼭 모두 다 써서 표현해야 한다는건 아니다. [1,2,5]라면 1,2,5 모두 써서 n원 표현하라는게 아니라 1,2,5 중 일부로만 표현하는 것도 포함! 쓸 수 있는 화폐 범위가 [1,2,5]라는 것이다.)
    • 예제의 [1,2,5] 화폐를 예를 들면 arr[1][3] 은 [1,2] 화폐 만으로 3원을 표현할 수 있는 경우의 수
  • 1️⃣ arr[i - 1][j]
    • money[i]를 포함하지 않고 { money[0], money[1], .. , money[i - 1] } 화폐들로만 j원을 표현할 수 있는 경우의 수
      • 예제의 [1,2,5] 화폐를 예를 들면 arr[2][3] 은 [5]을 제외하고 오직 [1,2] 화폐 만으로 3원을 표현할 수 있는 경우의 수인 arr[1][3]을 포함한다.
  • 2️⃣ arr[i][j - money[i]]
    • money[i]를 꼭 포함해서 { money[0], money[1], .. , money[i] } 화폐들로 j원을 표현할 수 있는 경우들의 개수
    • 이는 곧 { money[0], money[1], .. , money[i] } 으로 j - money[i]을 표현하는 경우들의 개 수와 동일하다.
      • [2,3,5,7] 화폐로 9 원을 표현하는 경우의 수는 [2,3,5,7] 로 9 - 7 = 2 원을 표현하는 모든 경우들에 각각 9 만 더해주면 11 로 만들 수 있으니 [2,3,5,7] 로 9 - 7 = 2 원을 표현하는 경우의 수와도 같다.
        • [2,3,5,7] 로 2원을 표현하는 경우는 [2] 밖에 없다. 여기에 7을 붙이면 [2, 7] 이렇게 9원을 표현할 수 있게 된 것이다. 따라서 [2,3,5,7] 로 9원을 표현할 때 7을 꼭 포함하는 경우의 개수는 [2,3,5,7] 로 2원을 표현하는 경우의 개수와 같다.

점화식 규칙 요약

• arr[4][8] [1,2,3,4,5] 으로 8 원을 표현하는 경우의 수
  • 5 을 포함하지 않고 👉 [1,2,3,4] 만으로 8 원을 표현하는 경우의 수 👉 arr[3][8]
  • 5 을 반드시 포함하여서 👉 [1,2,3,4,5] 만으로 8 원을 표현하는 경우의 수
    • 이는 곧 [1,2,3,4,5] 만으로 8 - 5 = 3 원을 표현하는 경우의 수와도 같다. 이 경우들에 5 를 더하면 8 이 되기 때문이다. 👉 arr[4][3]
      • [1,2,3,4,5]로 3을 표현하는 경우 : [1,1,1], [1, 2]
        • 여기에 5만 붙여주면 [1,1,1,5], [1, 2, 5] 이렇게 그대로 5를 꼭 포함해서 [1,2,3,4,5]로 8을 표현하는 경우가 될 수 있기 때문에 두 경우의 수가 같은 것이다.

이 문제에서의 정답은 모든 화폐를 다 써서 n을 표현한 arr[money.size() - 1][n] 값이 되겠다.

✈ 2 차 풀이 (DP) ⏰시간, 메모리 초과

#include <string>
#include <vector>
#include <algorithm>

using namespace std;

int solution(int n, vector<int> money) {
    int answer = 0;
    
    vector<vector<int>> dp(money.size(), vector<int>(n + 1, 0));

    dp[0][0] = 1;
    for(int j = 1; j <= n; j++)
        dp[0][j] = ((j % money[0] == 0) ? 1 : 0);
    
    for(int i = 1; i < money.size(); i++){
        for (int j = 0; j <= n; j++){
            if (j >= money[i])
                dp[i][j] = (dp[i - 1][j] + dp[i][j - money[i]]) % 1000000007; 
            else if (j < money[i])
                dp[i][j] = dp[i - 1][j] % 1000000007;
        }
    }
    
    answer = dp[money.size() - 1][n];
    return answer;
}

첫 행의 점화식 👉 money[0]원 화폐 하나로만 j = 0,1,..,n 을 표현할 수 있는 경우

    dp[0][0] = 1; // money[0]으로 0 을 표현할 수 있는 방법은 1 개. (즉 빈 조합..! money[0]를 사용하지 않는 것.) 위에서도 언급했지만 money 원소를 무조건 다 쓰지 않아도 됨..! [2, 5] 화폐 조합은 2 만 쓰고 5 를 쓰지 않는 것도 포함이다.
    for(int j = 1; j <= n; j++) // i = 0 첫 행의 점화식. (즉 money[0] 만으로 j 를 표현하는 경우의 수)
        dp[0][j] = ((j % money[0] == 0) ? 1 : 0);

• j 가 money[0] 의 배수일 때
  • arr[0][j] = 1
    • money[0]가 10 이라면 10의 배수들의 수는 다 10원 여러개로 표현할 수 있는 수이니 1가지
• j 가 monwy[0] 의 배수가 아닐 때
  • arr[0][j] = 0
    • money[0] 하나로 money[0] 의 배수가 아닌 수들을 표현할 순 없다.

    for(int i = 1; i < money.size(); i++){ // i = 0 첫행 이외의 행들의 점화식
        for (int j = 0; j <= n; j++){
            if (j >= money[i])
                dp[i][j] = (dp[i - 1][j] + dp[i][j - money[i]]) % 1000000007; 
            else if (j < money[i])
                dp[i][j] = dp[i - 1][j] % 1000000007;
        }
    }

    answer = dp[money.size() - 1][n];
    return answer;

[1,2,5] 에다가 n = 5일 때의 경우

	0	1	2	3	4	5
{ 1 }	1	1	1	1	1	1
{ 1, 2 }	1	1	💛1 + 1 = 2	1 + 1 = 2	1 + 1 = 2	1 + 2 = 3
{ 1, 2, 5 }	1	1	2	2	2	💛3 + 1 = 4

[2,3,5,7] 에다가 n = 11일 때의 경우

	0	1	2	3	4	5	6	7	8	9	10	11
{ 2 }	1	0	1	0	1	0	1	0	1	0	1	0
{ 2, 3 }	1	0	1	💛0 + 1 = 1	1 + 0 = 1	0 + 1 = 1	1 + 1 = 2	0 + 1 = 1	1 + 1 = 2	0 + 2 = 2	1 + 1 = 2	0 + 2 = 2
{ 2, 3, 5 }	1	0	1	1	1	💛1 + 1 = 2	2 + 0 = 2	1 + 1 = 2	2 + 1 = 3	2 + 1 = 3	2 + 2 = 4	2 + 2 = 4
{ 2, 3, 5, 7 }	1	0	1	1	1	2	2	💛2 + 1 = 3	3 + 0 = 3	3 + 1 = 4	4 + 1 = 5	4 + 1 = 5

• j < money[i] 경우 점화식 👉 arr[i][j] = arr[i - 1][j]
  • 표의 💛 전의 열들
    • 이 경우엔 j - money[i] 가 음수가 되기 때문에 2️⃣번인 money[i]를 “포함”하는 경우의 수를 구할 수가 없다.
    • [2, 3, 5]에서 2️⃣ 5를 꼭 “포함”하여 3을 만드는 경우는 [2, 3] 만으로 만든 조합에 5 를 포함해서 3으로 만들 수 있어야 하는데 그럼 [2, 3] 으로 -2를 만들어야 한다는 얘기니 불가능하다.
  • 따라서 이 경우엔 그대로 money[i]를 제외한 수들 끼리 j를 표현한 arr[i - 1][j] 값을 그대로 물려 받게 된다.
• j >= money[i] 경우 점화식 👉 arr[i][j] = arr[i - 1][j] + arr[i][j - money[i]]
  • 표의 💛부터 해당하는 열들
    • 1️⃣ arr[i - 1][j]
      • money[i]를 포함하지 않고 { money[0], money[1], .. , money[i - 1] } 화폐들로만 j원을 표현할 수 있는 경우의 수
        • 예제의 [1,2,5] 화폐를 예를 들면 arr[2][3] 은 [5]을 제외하고 오직 [1,2] 화폐 만으로 3원을 표현할 수 있는 경우의 수인 arr[1][3]을 포함한다.
    • 2️⃣ arr[i][j - money[i]]
      • money[i]를 꼭 포함해서 { money[0], money[1], .. , money[i] } 화폐들로 j원을 표현할 수 있는 경우들의 개수
      • 이는 곧 { money[0], money[1], .. , money[i] } 으로 j - money[i]을 표현하는 경우들의 개 수와 동일하다.
        • [2,3,5,7] 화폐로 9 원을 표현하는 경우의 수는 [2,3,5,7] 로 9 - 7 = 2 원을 표현하는 모든 경우들에 각각 9 만 더해주면 11 로 만들 수 있으니 [2,3,5,7] 로 9 - 7 = 2 원을 표현하는 경우의 수와도 같다.
          • [2,3,5,7] 로 2원을 표현하는 경우는 [2] 밖에 없다. 여기에 7을 붙이면 [2, 7] 이렇게 9원을 표현할 수 있게 된 것이다. 따라서 [2,3,5,7] 로 9원을 표현할 때 7을 꼭 포함하는 경우의 개수는 [2,3,5,7] 로 2원을 표현하는 경우의 개수와 같다.

근데 위와 같이 2 차원 테이블을 사용하면 시간 초과가 발생한다. 메모리 사용량도 상당한 것을 확인할 수 있다.

✈ 3 차 풀이 ⭕ (DP)

#include <string>
#include <vector>
#include <algorithm>

using namespace std;

int solution(int n, vector<int> money) {
    int answer = 0;
    
    vector<int> dp(n + 1);

    dp[0] = 1;
    for(int i = 1; i <= n; i++)
        dp[i] = ((i % money[0] == 0) ? 1 : 0);
    
    for(int i = 1; i < money.size(); i++)
        for (int j = 0; j <= n; j++){
            if (j >= money[i])
                dp[j] = (dp[j] + dp[j - money[i]]) % 1000000007;
          /*else if (j < money[i])
                dp[j] = dp[j] % 1000000007;*/

    answer = dp[n];
    return answer;
}

• 공간 효율성 ⭐
  • 이 DP 테이블에 2 가지 정보가 들어가는 것은 맞지만 사실 2차원 배열로 구현하지 않고 1차원 배열만 사용해도 가능하다.
    • 1️⃣ arr[i - 1][j] : 점화식엔 직전 행의 정보가 필요하다.
      • 직전 행은 사실 1차원 배열의 “업뎃 전 직전의 값” 으로 대체 가능하다. 즉 arr[j]를 업데이트 하기 전 기존의 arr[j]으로 생각할 수도 있겠다.
    • 2️⃣ arr[i][j - moeny[i]] : 같은 행의 이전 열인 왼쪽 원소들 정보가 필요
      • 이건 정말 1차원 배열로 충분. arr[j - money[i]]와 같다.
• 시간 효율성
  • 2 차원 배열도 접근 자체가 1 차원 배열보단 시간이 더 걸리는 듯 하다.

arr[i][j] = arr[i - 1][j] + arr[i][j - money[i]]

• j < money[i] 경우 점화식
  • arr[i][j] = arr[i - 1][j] 👉 arr[j] = arr[j]
    • 직전 행의 정보만 그대로 옮겨오면 되기 때문에 1 차원 배열로는 그냥 업뎃 전 직전의 값이다.
    • 자기 자신을 대입하는게 끝이라 이 경우엔 주석 처리 해주었다. 그래서 이렇게 1 차원 배열로 바뀌니 j < money[i] 경우를 따로 처리해주지 않아도 괜찮아졌다.
• j >= money[i] 경우 점화식
  • arr[i][j] = arr[i - 1][j] + arr[i][j - money[i]] 👉 arr[j] = arr[j] + arr[j - money[i]]

🔥 이 문제로 깨달은 교훈

1. 입력 크기가 상당하다면 어떤 점화식의 관계가 있진 않을까, DP 로 풀 수 있진 않을까 고민을 해보자.
   • 시간 복잡도를 늘 생각하고 접근하자.
2. 2 차원 테이블을 채우는 DP 문제라도 1 차원 배열에서 표현할 수 있는지를 따져보자. (공간 시간 효율성을 더 높일 수 있는지)
   • 직전 행에 대한 정보와 같은 행의 왼쪽 열들에 대한 정보 정도만 점화식에 쓰인다면 충분히 1차원 배열로 표현할 수 있다.
3. 점화식 규칙은 B = A + !A 이런식으로 세울 수 있는지도 따져보자.
   • [1,2,5]로 만들 수 있는 j원 = 5를 포함하지 않고 [1,2]로만 j원 만들기 + 5를 포함하고 [1,2,5]로 j원 만들기
   • 근데 여기서 이미 이전에 구한 테이블 원소 값으로 대체할 수 있는지를 고민해봐야 한다. 후자인 “5를 포함하고 [1,2,5]로 j원 만들기” 의 경우의 수는 “[1,2]로 5-0=0원 만들기”의 경우의 수와도 같다.

---

🌜 개인 공부 기록용 블로그입니다. 오류나 틀린 부분이 있을 경우 
언제든지 댓글 혹은 메일로 지적해주시면 감사하겠습니다! 😄

맨 위로 이동하기

Programmers 카테고리 내 다른 글 보러가기