Atcoder解いてみた AtCoder Beginner Contest C - Strange Bank

AtCoder Beginner Contest C - Strange Bank

問題はこちら

回答

N円というのがナップザックの要領
ただ、コインの種類が固定じゃないため、少し混乱した
普段とは少し違うナップザックDPの書き方を学んだ

#include <iostream>
#include <string>
#include <map>
#include <unordered_map>
#include <cstring>
#include <cmath>
#include <algorithm>
#include <vector>
#include <queue>
#include <stack>
#include <limits.h>
#include <bitset>
#include <list>
#include <set>
#include <numeric>
#include <tuple>

int N, H;
std::vector<int> A;
std::vector<int> B;

const long long inf = 1e18;

int main()
{
	std::cin.tie(0);
	std::ios::sync_with_stdio(false);

	std::cin >> N;

	// i円引き出すときの最小回数
	std::vector<long long> dp(N+1, inf);
	dp[0] = 0;

	for (int i = 0; i < N; i++) {
		// 1円引き出す
		dp[i + 1] = std::min(dp[i + 1], dp[i] + 1);

		// 6のべき乗円引き出す
		long long sixPow = 6;
		while (i+sixPow <= N) {
			dp[i + sixPow] = std::min(dp[i + sixPow], dp[i] + 1);
			sixPow *= 6;
		}

		// 9のべき乗円引き出す
		long long ninePow = 9;
		while (i + ninePow <= N) {
			dp[i + ninePow] = std::min(dp[i + ninePow], dp[i] + 1);
			ninePow *= 9;
		}
	}

	std::cout << dp[N] << std::endl;


	return 0;
}