1785번: 보드 게임

https://www.acmicpc.net/problem/1785


$O((\log n)^4)$

주어진 방법으로 지폐단위를 만들면 큰 지폐 단위부터 순서대로 최대한 환전했을 때 필요한 지폐 총 개수가 최소가 된다.
이러한 특성을 이용하여 다음 점화식을 통해 DP를 한다.

dp[i][j][k][l]: 2,3,4,5를 각각 i,j,k,l번 곱해 나온 지폐 단위 + 이후 만든 더 큰 지폐 단위를 이용하여 나머지를 최소화하며 환전할 때 필요한 최소 지폐 수
p = 2^i * 3^j * 4^k * 5^l이면
dp[i][j][k][l] = min(
dp[i+1][j][k][l] + n/p%2,

dp[i][j+1][k][l] + n/p%3,

dp[i][j][k+1][l] + n/p%4,

dp[i][j][k][l+1] + n/p%5)

답은 dp[0][0][0][0]

#include<cstdio>
#include<algorithm>
using namespace std;
long long n, dp[60][38][30][26];
int k, c[6];
long long f(long long x, int y) {
    if (!x || !y) return x;
    long long &ret = dp[c[2]][c[3]][c[4]][c[5]];
    if (ret) return ret;
    ret = 1e18;
    for (int i = 2; i <= 5; i++) {
        c[i]++;
        ret = min(ret, x%i + f(x / i, y - 1));
        c[i]--;
    }
    return ret;
}
int main() {
    scanf("%lld %d", &n, &k);
    printf("%lld", f(n, k - 1));
    return 0;
}