BOJ 13137 - Exchange Problem

BOJ 13137 - Exchange Problem

그냥 생각하다보니 $2P_N$ 까지만 따져보면 되겠다고 추측이 되어서 그렇게 풀었다.

이건 증명이 어려워보이지만 이 정보를 직접 주는 BOJ 15423 문제를 먼저 푼다면 이것이 참임을 알 수 있다.

일반 동전 문제처럼 $O(N \cdot 2P_N)$ 로 미리 최솟값 배열을 전처리해두고

$dp[i]=dp[i-max]+1$ 가 원래 전처리해둔 것과 동일한지 비교하며 검사해준다.

void solve() {
   int n;
   cin >> n;
   vi a(n);
   fv(a);
   int m = a.back();

   vi dp(2 * m + 1, 1e9), dp2(2 * m + 1, 1e9);

   dp[0] = 0;
   for (int i = 0; i < n; i++) {
      for (int j = a[i]; j <= 2 * m; j++) {
         if (dp[j - a[i]] != 1e9)
            mina(dp[j], dp[j - a[i]] + 1);
      }
   }
   for (int i = 0; i <= 2 * m; i++) {
      if (dp[i] == 1e9) {
         cout << "No";
         return;
      }
   }
   dp2[0] = 0;

   for (int i = 1, j = -1; i <= 2 * m; i++) {
      while (j + 1 < n && a[j + 1] <= i) j++;
      if (j == -1) {
         cout << "No";
         return;
      }
      int mx = a[j];

      dp2[i] = dp2[i - mx] + 1;
      if (dp[i] != dp2[i - mx] + 1) {
         cout << "No";
         return;
      }
   }
   cout << "Yes";
}