백준 14211번 Kas

문제 링크입니다: https://www.acmicpc.net/problem/14211

백준 1126번 같은 탑(http://jaimemin.tistory.com/717)과 동일한 문제였습니다.

(인덱스)와 (두 사람의 수표 보유량 차)를 기준으로 하는 DP 문제로 접근하면 쉽게 풀 수 있는 문제였습니다.

어차피 두 사람이 나누지 못하는 수표는 룰렛을 통해 두배로 만든 다음에 반씩 나누어가지기 때문에  (동일하게 나눈 수표 가치의 합) + (남은 수표)를 출력해줘야 정답입니다!

#include <iostream>

#include <algorithm>

#include <cstring>

using namespace std;

 

const int MAX = 500 + 1;

const int INF = 987654321;

 

int N, sum;

int money[MAX];

int cache[MAX][50000 + 1];

 

int split(int idx, int difference)

{

        //기저 사례: 동일하게 나눌 수 없는 경우

        if (difference > sum / 2)

                 return -INF;

        //기저 사례: 동일하게 나누지 않은 경우

        if (idx == N && difference)

                 return -INF;

 

        //동일하게 나눈 경우: 조건 성립

        if (idx == N && !difference)

                 return 0;

 

        int &result = cache[idx][difference];

        if (result != -1)

                 return result;

 

        result = -INF;

        //해당 수표를 줍지 않은 경우

        result = max(result, split(idx + 1, difference));

        //해당 수표를 더 돈이 많은 쪽이 주운 경우

        result = max(result, split(idx + 1, difference + money[idx]));

        //해당 수표를 더 돈이 적은 쪽이 주운 경우

        //1. 해당 수표가 두 사람의 수표 가치 차이보다 큰 경우

        if (money[idx] > difference)

                 result = max(result, difference + split(idx + 1, money[idx] - difference));

        //2. 해당 수표가 두 사람의 수표 가치 차이보다 작은 경우

        else

                 result = max(result, money[idx] + split(idx + 1, difference - money[idx]));

        return result;

}

 

int main(void)

{

        ios_base::sync_with_stdio(0);

        cin.tie(0);

        cin >> N;

 

        for (int i = 0; i < N; i++)

        {

                 cin >> money[i];

                 sum += money[i];

        }

 

        memset(cache, -1, sizeof(cache));

        int result = split(0, 0);

        int remainder = sum - 2 * result;

        cout << result + remainder << "\n";

        return 0;

}

개발환경:Visual Studio 2017

지적, 조언, 질문 환영입니다! 댓글 남겨주세요~