SPOJ - Bytelandian Gold Coins Problem Solution

SPOJ - BYTELANDIAN GOLD COINS (Famous DP Problem) solution

Solution:-

#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define MAX 100010
ll arr[MAX+5],i,N;

ll cal_max(int N)
{
    if(N<MAX)
        return arr[N];

    else if(N/2+N/3+N/4<=N)
        return N;
    else
        return cal_max(N/2)+cal_max(N/3)+cal_max(N/4);
}

int main()
{
    arr[0]=0;
    arr[1]=1;
    arr[2]=2;
    arr[3]=3;
    for(i=4;i<=MAX;i++)
        arr[i]=max(i,arr[i/2]+arr[i/3]+arr[i/4]);

    while(scanf("%lld",&N)==1)
    cout<<cal_max(N)<<endl;
    return 0;

}