[문제풀이] 백준 2293 - 동전1

📢 문제

https://www.acmicpc.net/problem/2293

📢 알고리즘

DP(동적 계획법)

📢 풀이

처음에 했던 풀이(메모리 초과)

#include <iostream>
#include <memory.h>

using namespace std;

int DP[101][10001]; // i번째 동전까지 고려했을 때 가치의 합이 l이 되도록 하는 경우의 수
int V[101];         //각 동전의 가치

int main()
{
  int n, k;
  cin >> n >> k;

  for (int i = 1; i <= n; i++)
  {
    cin >> V[i];
  }

  for (int i = 1; i <= n; i++)
  {
    DP[i][0] = 1;
  }

  for (int i = 1; i <= n; i++)
  {
    for (int l = 1; l <= k; l++)
    {
      if (i == 1)
      {
        if (l % V[1] == 0)
        {
          DP[1][l] = 1;
        }
        else
        {
          DP[1][l] = 0;
        }
      }
      else
      {
        // i번째 동전 사용 안(못)하는 경우
        DP[i][l] = DP[i - 1][l];

        // i번째 동전 사용하는 경우
        int p = 1;
        while (l - p * V[i] >= 0)
        {
          // l-V[i] == 0일땐 i번째 동전만 사용
          DP[i][l] += DP[i - 1][l - p * V[i]];
          p++;
        }
      }
    }
  }

  cout << DP[n][k];
}

백준 12865 평범한 배낭 문제에 감명받아서 비슷한 방법으로 풀었다가 메모리 초과...
메모리 제한이 4MB인데, 1KB=1024byte고, 1MB=1024MB 이니 당연한 결과다.
앞으로 문제풀기 전에 메모리 체크하자 ❗❗

---

제출한 풀이

#include <iostream>

using namespace std;

int DP[10001]; //가치의 합이 l이 되도록 하는 경우의 수
int V[101];    //각 동전의 가치

int main()
{
  int n, k;
  cin >> n >> k;

  for (int i = 1; i <= n; i++)
  {
    cin >> V[i];
  }

  //아무 동전도 선택하지 않은 경우 : 1가지
  DP[0] = 1;

  for (int i = 1; i <= n; i++)
  {
    for (int l = V[i]; l <= k; l++) // l>V[i]일땐 어차피 i번째 동전 선택 불가 -> DP값이 그대로일것
    {

      if (i == 1)
      {
        if (l % V[1] == 0)
        {
          DP[l] = 1;
        }
        else
        {
          DP[l] = 0;
        }
      }
      else
      {
        DP[l] += DP[l - V[i]];
      }
    }
  }

  cout << DP[k];
}

}

설명

먼저 동전 1에 대해서 10원을 만드는 경우의 수를 계산해준다.
1(=j)부터 10(=k)까지 dp[j] += dp[j - 1] 을 해준다.

동전 2에 대해서는 0원과 1원은 만들지 못하니 패스하고
j = 2부터 10(=k)까지 dp[j] += dp[j - 2] 를 해준다.

마찬가지로 동전 5에 대해서도
j = 5부터 10(=k)까지 dp[j] += dp[j - 5] 를 해준다.

정답은 dp[k] 를 출력해주면 된다.

---

도저히 모르겠어서 풀이를 참고했는데도 이해하는데 오랜 시간이 걸렸다.

• DP 배열을 1차원 배열로 두었다.
  • 오답 풀이에서는 (1번째 동전까지 고려했을 때 가치의 합이 l이 되도록 하는 경우의 수), (2번째 동전까지 고려했을 때 가치의 합이 l이 되도록 하는 경우의 수)... 를 모두 구별해서 저장했다. i번째 동전까지 고려했을 때의 경우의 수를 구할 때, i-1번째 동전까지 고려했을 때의 경우의 수를 가져오기 위함이었다.
  • 하지만 바로 전 단계의 DP값만을 가져올 거라면 굳이 전전단계의 DP값까지 저장해둘 필요가 없다.
  • 따라서 그냥 DP[l]값을 갱신하면 된다.

• for문에서 int l = V[i]부터 시작 -> if문 없이 outOfBound 문제 해결

  • 오답풀이에서는 if(l- p*V[i] >=0) 이라는 조건을 걸었다.DP[i - 1][l - p * V[i]]에 접근할때 outOfBound를 막기 위해서다.
  • 하지만 어차피 l>V[i]일땐 i번째 동전 선택이 아예 불가하기 때문에 DP값이 갱신되지 않으므로 for문을 l=V[i]부터 시작해도 된다.

• DP[l] += DP[l - V[i]];

  • 새로운 DP[l] = i번째 동전 사용 안(못)하는 경우(기존DP[l]) + i번째 동전을 사용하는 경우(DP[l - V[i]])
  • 사용하는 경우 = i번째 동전을 새로 1개 더 사용했을 때(DP[l-V[i]])
  • DP[l-V[i]]에 그 가치합을 만족시키기 위해 사용된 i번째 동전들도 고려됨
  • 따라서 업데이트된 DP[l]에는 i번째 동전들을 사용하는 경우가 모두 포함됨

---

📖 참고자료

https://danidani-de.tistory.com/5