[백준] 14607번 피자 (Large) (C++)

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

 

 

이 문제는 N개의 피자 개수가 입력되었을때 이 N을 a, b로 분리하면 즐거움을 a * b 만큼 얻을 수 있는데

 

이때 분리할 수 없을때 까지 분리하였을때 최대로 얻을 수 있는 즐거움을 출력하는 문제이다.

 

 

즐거움을 최대로 얻기 위해선 N의 피자를 둘로 나눌때 둘로 나눈 차이가 엄청 작아야 최댓값을 얻을 수 있다.

 

따라서 2로 나누었을때 나머지가 없는 경우는 몫이 a, b가 되며

나머지가 있는 경우 a, a+1이 된다.

 

이때 왼쪽 그림과 같이 최댓값을 구하는 과정은 분할정복 과정 처럼 재귀를 사용하여 구할 수 있다.

 

N의 크기가 최대 10^9 이기 때문에 map을 사용하여 memozation을 한다.

 

정답코드

#include <bits/stdc++.h>
using namespace std;
typedef pair<int, int> pii;
typedef long long ll;
#define endl "\n"
#define MAX 1e9

struct coordinate {
    int x;
    int y;
    int r;
};

int dx[] = {-1, 1, 0, 0, 1, -1, -1, 1};
int dy[] = {0, 0, -1, 1, -1, 1, -1, 1};
int N;
map<ll, ll> m;

ll solve(ll n) {
    if(m.count(n) > 0) return m[n];

    if(n % 2 == 0) {
       m[n] = (n / 2) * (n / 2) + (solve(n / 2) + solve(n / 2));
    }
    else m[n] = (n / 2) * (n / 2 + 1) + solve(n / 2) + solve(n / 2 + 1);

    return m[n];
}

void input() {
    cin >> N;

    m[1] = 0;

    cout << solve(N);
}

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0), cout.tie(0);

    input();
}

 

 

회고록

처음엔 분할정복이라 생각을 못하고 우선순위 큐(최대힙)을 사용하여 루트를 꺼내어 계속 2로 나눠주며 계산해야겠다고 생각하였다.

하지만 힙에 들어가는 크기가 N log N 만큼 들어가기 때문에 시간초과가 난다. 따라서 분할정복을 사용하여

log N 만큼 최적화를 하여 계산해야한다.