Help us understand the problem. What is going on with this article?

AtCoder Beginner Contest 099_C Strange Bank

AtCoder Beginner Contest 099_C Strange Bank

dpかなとは思ったけど累乗の処理をどうするべきかがわからなかった...
ポイントはここでした。
whileでpower=1として一周するたびに6倍していくんですね。
power <= iとなった時点で終了します。

int power = 1;
  while(power <= i) {
    dp[i] = min(dp[i], dp[i-power] + 1);
    power *= 6;
  }

上記の式で1円を使ったことも含まれているので、
あとは9円versionを考えて、これとおんなじものを*=9として実装すれば良い。

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using pii = pair<int, int>;
int dx[4] = {1, 0, -1, 0};
int dy[4] = {0, 1, 0, -1};
const long long INF = 1LL << 60;
const ll C = 1000000000+7;


ll dp[100010];
int main() {
    int N;
    cin >> N;
    dp[0] = 0;

    for(int i=1; i<=100000; i++) {
        dp[i] = INF;
        int power = 1;
        while(power <= i) {
            dp[i] = min(dp[i], dp[i-power] + 1);
            power *= 6;
        }
        power = 1;
        while(power <= i) {
            dp[i] = min(dp[i], dp[i-power] + 1);
            power *= 9;
        }
    }
    cout << dp[N] << endl;
}

おしまい。
dpだけのコンテストがあったので週末はこれをやろう...
しばらくBeginner Contestが無い。精進期ですね。

akilax
営業社員からエンジニアになりました。
Why not register and get more from Qiita?
  1. We will deliver articles that match you
    By following users and tags, you can catch up information on technical fields that you are interested in as a whole
  2. you can read useful information later efficiently
    By "stocking" the articles you like, you can search right away