백준 10611번 PŠENICA

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

처음에는 덱을 이용하여 직접 시뮬레이션을 하였더니 시간 복잡도가 O(N^2)이 나와 TLE가 발생했던 문제였습니다.

문제의 입력은 최대 100,000개이기 때문에 O(N)으로 풀어야 AC를 받을 수 있는 문제였습니다.

알고리즘은 아래와 같습니다.

1. {밀의 높이, 해당 높이 등장한 횟수}를 저장하는 덱을 선언하고 밀의 높이 오름차순으로 저장합니다.

2. 애초에 밀의 높이 종류가 3 미만이면 Slavko가 이깁니다. 따라서, Slavko가 이긴다고 가정합니다.

3. 직접 시뮬레이션을 하지 않으려면 최소높이 밀의 개수와 최대높이 밀의 개수를 파악해야합니다.

i) 최소높이 밀의 개수가 최대 높이 밀의 개수보다 작거나 같다면 Mirko가 마지막 움직임을 가집니다.

a) 우선 Mirko는 할 수 있는 움직임을 다 끝내고 Slavko는 Mirko의 움직임보다 하나 덜 움직입니다.

b) Mirko가 다 움직이고 밀의 높이 종류가 1이라면 게임이 끝나므로(Slavko가 바꿔야할 최대높이 밀은 여전히 있지만 Mirko가 바꿔야할 최소높이 밀은 이제 없으므로 밀의 높이 종류가 2개 뿐입니다.)

c) Mirko가 다 움직이고도 게임이 끝나지 않으면 Slavko도 마지막 움직임을 가져갑니다.

ii) 최소높이 밀의 개수가 최대 높이 밀의 개수보다 크면 Slavko가 이긴다고 가정한 상태이므로 둘 다 한번에 움직임을 가져갑니다.

4. 덱의 사이즈가 3 미만이라면 3번을 종료하고 출력형식에 맞게 답을 출력합니다.

#include <iostream>

#include <deque>

using namespace std;

 

const int MAX = 100000 + 1;

 

int visited[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 height;

                 cin >> height;

 

                 visited[height]++;

        }

 

        deque<pair<int, int>> dq; //height, cnt

        for (int i = 1; i < MAX; i++)

                 if (visited[i])

                         dq.push_back({ i, visited[i] });

 

        bool slavkoWin = true;

        if (dq.size() >= 3)

        {

                 while (1)

                 {

                         //Mirko의 움직임이 마지막

                         if (dq.front().second <= dq.back().second)

                         {

                                 pair<int, int> minHeight = dq.front();

                                 dq.pop_front();

                                 pair<int, int> maxHeight = dq.back();

                                 dq.pop_back();

 

                                 dq.front().second += minHeight.second;

                                 maxHeight.second -= (minHeight.second - 1);

                                 dq.back().second += (minHeight.second - 1);

 

                                 //최소 3개의 높이인데 Mirko의 움직임이 마지막이므로

                                 //이제 2개의 높이 밖에 없다

                                 if (dq.size() == 1)

                                 {

                                          slavkoWin = false;

                                          //Slavko가 바꾸다만 제일 높은 밀

                                          dq.push_back(maxHeight);

                                          break;

                                 }

 

                                 //Mirko의 움직임으로 끝나지 않았으므로

                                 //Slavko의 움직임

                                 maxHeight.second--;

                                 dq.back().second++;

                                 if (maxHeight.second)

                                          dq.push_back(maxHeight);

                         }

                         //Slavko 움직임이 마지막

                         else

                         {

                                 pair<int, int> minHeight = dq.front();

                                 dq.pop_front();

                                 pair<int, int> maxHeight = dq.back();

                                 dq.pop_back();

 

                                 minHeight.second -= maxHeight.second;

                                 dq.front().second += maxHeight.second;

                                 dq.back().second += maxHeight.second;

                                 dq.push_front(minHeight);

                         }

                         if (dq.size() < 3)

                                 break;

                 }

        }

 

        if (slavkoWin)

                 cout << "Slavko\n";

        else

                 cout << "Mirko\n";

 

        cout << dq.front().first << " " << dq.back().first << "\n";

        return 0;

}

개발환경:Visual Studio 2017

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