ABC99 C - Strange Bank

問題概要

  • ある銀行では、お金の引き出しを難しくするために、一回の操作で引き出せる金額が以下のいずれかである。
    • 1 円
    • 6 円、 62 円、 63 円
    • 9 円、 92 円、 93 円

この銀行からちょうどN 円を引き出す時の最小引き出し回数を求めよ。

制約

  • 1 ≤ N ≤ 100000
  • N は整数

問題へのリンクはこちら

考えたこと

  1. 貪欲法でいけないかどうか Nを超えない最大の6または9の倍数で引いていく方針を考える。しかしながら、N = 12の時、この方針だとうまくいかないため、(12→3→2→1→0 よりも12→6→0 の方が回数が少ないため。) =>違う方針を検討

  2. DPを用いる。

  3. n-1回目からn回目への遷移を考えると、1円を引けばいいため、回数は一回増える。
  4. n-6回目からn回目への遷移は、6円を引けばいいため、回数が一回増える

このような遷移を6,9のべき乗に対して考えてあげた上で、回数の最小値がdp[N] の答えとなる。

#include<bits/stdc++.h>
using namespace std;
int NMAX = 100000;
int dp[NMAX+10];

int main() {
  int N; cin >> N;
  dp[0] = 0;
  for(int n = 0; n <= NMAX; ++n) {
    dp[n] = NMAX;
    int power = 1;
    while(power <= n) {
      dp[n] = min(dp[n], dp[n-power] + 1);
      power *= 6;
    }
    power = 1;
    while(power <= n) {
      dp[n] = min(dp[n], dp[n-power] + 1);
      power *= 9;
    }
  cout << dp[N] << endl;
  return 0;
}