[14607번] 피자 (Large)

문제 출처 :

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

알고리즘 분석 :

문제 해결에 필요한 사항

1. Dynamic Programming

2. 점화식 세우는 방법

dp 점화식을 세워 문제를 해결한다.

dp[i] :: i번째 최대 행복

dp[i] = (i / 2) * (i / 2) + dp[i / 2] + dp[i / 2]라는 방식을 통해 해결 할 수 있다.

반씩 나누었을 때 곱 + 이전 dp값을 이용하여 현재 dp를 갱신해주면 된다.

여기서 Small문제는 for문으로 해결되지만 Large문제는 메모이제이션을 통해 DP를 구해주면 된다.

소스 코드 : 

#include <iostream>
#include <cstdio>
#include <map>
 
using namespace std;
 
typedef long long ll;
 
int dp[12];
map<ll, ll> mp;
 
ll dy(ll n)
{
    if (n == 1 || mp[n])
        return mp[n];
 
    if (n % 2 == 1)
        mp[n] = dy(n / 2) + dy(n / 2 + 1) + (n / 2) * (n / 2 + 1);
    else
        mp[n] = dy(n / 2) + dy(n / 2) + (n / 2) * (n / 2);
 
    return mp[n];
}
int main()
{
    ll n;
 
    scanf("%lld", &n);
    mp[1] = 0;
    mp[2] = 1;
 
    dy(n);
 
    printf("%lld",mp[n]);
    return 0;
}
 
//                                                       This source code Copyright belongs to Crocus
//                                                        If you want to see more? click here >>