백준 1398 - 동전 문제

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

1398번: 동전 문제

 

힌트 1

동전 교환 문제를 그리디 하게 풀려면 주어진 동전들의 값이 서로 서로소가 아니어야 함이 알려져 있다.

 

일단 적당한 범위 안에서의 답을 dp로 모두 구해놓고 dp로 도출한 해와 그리디로 푼 해의 차이를 비교해 보자. 유의미한 결과를 얻을 수 있는가?

힌트 2

30, 40, 80, 90

 

 

해설

적당히 큰 범위 내에서 dp로 해를 찾은 뒤 그리디하게 구한 해와 비교해보자.

 

그러면 다음 사실을 발견할 수 있다.

 

해당 문제의 답을 $f(x)$라 했을 때

 

$f(30) = f(3000) = ... = f(30 \times 100^{i})$

$f(40) = f(4000) = ... = f(40 \times 100^{i})$

$f(80) = f(8000) = ... = f(80 \times 100^{i})$

$f(90) = f(9000) = ... = f(90 \times 100^{i})$

 

위 식들이 성립한다.

 

여기에서 그치지 않고 100 미만의 다른 수 역시 100의 제곱 단위로 필요한 동전의 수가 같음을 발견할 수 있다.

 

그렇다는 것은 주어진 $N$에서 100의 단위로 답을 끊어 계산할 수 있다는 뜻이다. 따라서 100 미만의 범위의 해를 dp로 구해놓고 100씩 나눠가며 $f(N \mod 100)$를 더하면 최종 답을 구할 수 있다.

솔루션

#pragma GCC target("fma,avx,avx2,bmi,bmi2,lzcnt,popcnt")
#pragma GCC optimize("O3,unroll-loops")

#include "bits/stdc++.h"

using namespace std;

using ll = int_fast64_t;
using pii = pair<int, int>;

int tc;
vector<ll> vec;
int dp[111];

void ps(__int128 tmp, int mul)
{
  while (tmp <= 1000000000000000LL)
  {
    vec.push_back((ll)tmp);
    tmp *= mul;
  }
}

void solve()
{
  cin >> tc;

  ps(1, 10);
  ps(25, 100);

  for (int i = 1; i <= 100; i++)
  {
    dp[i] = 1e9;
  }

  sort(begin(vec), end(vec));

  for (ll i : vec)
  {
    for (ll j = i; j <= 100; j++)
    {
      dp[j] = min(dp[j], dp[j - i] + 1);
    }
  }

  while (tc--)
  {
    ll x;
    cin >> x;
    int ans = 0;
    while (x >= 100)
    {
      ans += dp[x % 100];
      x /= 100;
    }
    ans += dp[x];
    cout << ans << '\n';
  }
}

int main()
{
#ifdef LOCAL
  freopen("input.txt", "r", stdin);
//  freopen("output.txt", "w", stdout);
#endif
  cin.tie(nullptr);
  ios::sync_with_stdio(false);

  solve();
}