ABC099 C問題

Question

前提・実現したいこと

ABC099 C問題
配るDPで実装したところWAが出てしまいましたが、どこがダメなのか分かりません。
解説はメモ化再帰で実装しているので原因解明の参考にはなりませんでした。

発生している問題・エラーメッセージ

いくつかのテストケースでWAが出ます

該当のソースコード

#define _USE_MATH_DEFINES
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

int main() {
    ll N;
    cin >> N;
    // dp[i]：i円引き出すのに必要な最小の回数
    vector<ll> dp(N + 1);
    for (ll i = 1; i < N + 1; i++) {
        dp[i] = i;
    }
    for (ll i = 1; i < N + 1; i++) {
        for (ll a = 6; i + a < N + 1; a *= 6) {
            dp[i + a] = min(dp[i + a], dp[i] + 1);
        }
        for (ll b = 9; i + b < N + 1; b *= 9) {
            dp[i + b] = min(dp[i + b], dp[i] + 1);
        }
    }
    cout << dp[N] << endl;
}

Answer 1

入力に6を渡した場合、正しい出力は1ですが、このコードだと6が返ります。

Comments

[a9uaDrops]

回答ありがとうございます。
指摘された部分を満たすようにコードを書き換えたらACできました。