ABC_099_C - Strange Bank

[zeikar]

Problem link

https://atcoder.jp/contests/abc099/tasks/abc099_c

Problem Summary

한 번에 인출할 수 있는 액수가 정해져 있고, 주어진 돈을 최소 몇 번만에 인출할 수 있는지 구하는 문제.

Solution

전형적인 DP 문제.
간단하게

dp[n] = n을 인출할 수 있는 최소 횟수.

로 정의하고 돌려주면 된다.

에디토리얼 보니 그리디로도 풀 수 있다.

Source Code

#include <iostream>
#include <cstring>
using namespace std;

int dp[100001];

int main() {
	int N;
	cin >> N;

	for (int i = 1; i <= N; i++)
	{
		dp[i] = 987654321;

		for (int j = 6; j <= i; j *= 6)
		{
			dp[i] = min(dp[i], dp[i - j] + 1);
		}
		for (int j = 9; j <= i; j *= 9)
		{
			dp[i] = min(dp[i], dp[i - j] + 1);
		}

		dp[i] = min(dp[i], dp[i - 1] + 1);
	}

	cout << dp[N] << endl;
}