백준 2923번 숫자 게임

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

그리디하게 접근해야함을 증명해야하는 알고리즘 문제였습니다.

처음에 A의 Max와 B의 Min을 더해주면 답이라고 접근했고 이후에는 모르겠어서 솔루션을 참고했습니다.

그리디하게 접근하기 위해 아래와 같이 가정을 하고 증명해 나가야합니다.

i) A의 Max와 B의 Min을 더하는 것이 가장 큰 값이다

ii) A의 Max와 B의 Min을 더하는 것은 가장 큰 값이 아니다.

i)와 같이 가정을 했을 경우 B의 다른 값을 넣어도 최적의 값에서 감소시킬 수 없다는 것이 자명합니다. 

따라서, i)와 같은 경우에는 B의 Min과 동일한 값을 더해서 똑같은 값을 구하는 것이 최적입니다.

ii)와 같이 가정을 했을 경우 Ax + Bx 가 가장 큰 값이라고 가정을 합니다.

하지만 우리는 결론적으로 A의 Max와 B의 Min을 쪼갬으로써 더 큰 값을 만들어낼 수 있습니다.

A의 Max와 B의 Min을 쪼개면 아래와 같이 두 가지 경우가 발생하는데 한 가지 경우만 성립합니다.

a) Ax + B의 Min은 Ax + Bx 이하라는 것은 자명합니다.(∵ B의 Min <= Bx)

b) A의 Max + Bx는 Ax + Bx 이상이라는 것이 자명합니다.(∵ A의 Max >= Ax)

따라서 두 가지 가정 중 ii)만 성립하므로 매 쿼리마다 A의 Max와 Bx를 더하도록 그리디하게 접근하면 AC를 받을 수 있는 문제였습니다.

#include <iostream>

#include <vector>

#include <algorithm>

using namespace std;

 

const int MAX = 100 + 1;

 

int A[MAX], B[MAX];

 

int main(void)

{

        ios_base::sync_with_stdio(0);

        cin.tie(0);

        int N;

        cin >> N;

 

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

        {

                 int a, b;

                 cin >> a >> b;

 

                 vector<int> vA(MAX), vB(MAX);

                 A[a]++;

                 B[b]++;

                 for (int j = 0; j < MAX; j++)

                 {

                         vA[j] = A[j];

                         vB[j] = B[j];

                 }

 

                 int result = 0;

                 //aIdx는 제일 큰 값, bIdx는 제일 작은 값

                 int aIdx = 100, bIdx = 1;

 

                 while (aIdx >= 1 && bIdx < MAX)

                 {

                         while (aIdx >= 1 && vA[aIdx] == 0)

                                 aIdx--;

                         while (bIdx < MAX && vB[bIdx] == 0)

                                 bIdx++;

 

                         //모든 수 체크했을 때

                         if(aIdx == 0 || bIdx == MAX)

                                 break;

 

                         //최댓값 업데이트

                         result = max(result, aIdx + bIdx);

 

                         if (vA[aIdx] > vB[bIdx])

                         {

                                 vA[aIdx] -= vB[bIdx];

                                 vB[bIdx] = 0;

                         }

                         else

                         {

                                 vB[bIdx] -= vA[aIdx];

                                 vA[aIdx] = 0;

                         }

                 }

 

                 cout << result << "\n";

        }

        return 0;

}

개발환경:Visual Studio 2017

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