NYPC2024 문제 - 게임

NYPC2024 게임 문제 풀이를 진행하였습니다.
NYPC문제는 BIKO를 통하여 풀었습니다

문제 해석

문제를 읽으면 아래와 같은 해석이 가능합니다.

핑크빈과 블랙빈이 문자 0과 1로 구성된 길이 N인 문자열을 가지고 게임을 진행합니다
둘은 각각 K번 턴을 진행하며 핑크빈이 먼저 시작합니다.
각 턴에서 문자열에서 임의의 한 글자를 제거합니다. 문자열 중간에 있는 글자를 제거하면 남은 부분들이 이어져 하나의 문자열이 됩니다.
턴이 모두 끝나고 남은 문자열을 이진수로 해석했을 때, 핑크빈은 가장 작은 값이 되게 하려고 하며, 블랙빈은 가장 큰 값이 되게 하려고 한다.
핑크빈과 블랙빈이 모두 최선을 다한다고 생각했을 때 마지막에 남는 길이를 출력하는 프로그램을 작성해야 합니다.

문제 풀이

2진수로 되기 때문에 같은 길이일 경우 왼쪽에 1이 많을 경우 수가 커지며, 왼쪽에 0이 많을 수록 수가 작아집니다.
그러므로 수를 가장 작은 값을 만들기 위해 핑크빈은 최대한 왼쪽의 있는 1을 제거해주도록 하며, 1이 없을 경우 왼쪽의 0을 제거하도록 합니다.
가장 큰 값을 만들기 위해 블랙빈은 최대한 왼쪽에 있는 0을 제거해주도록 하며, 0이 없을 경우 오른쪽의 1을 제거하도록 합니다.

앞뒤 값을 빠르게 체크할 수 있는 deque를 사용하면 쉽게 해결할 수 있습니다.

전체 코드

#include <bits/stdc++.h>
#include <iostream>

using namespace std;

int main() 
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);

    int N, K;

    cin >> N >> K;

    string str;

    cin >> str;

    deque<int> dq[2];
	
    //0과 1이 존재하는 위치를 deque컨테이너에 저장해둠
    for (int i = 0; i < N; i++)
    {
        if (str[i] == '1')
        {
            dq[1].push_back(i);
        }
        else if (str[i] == '0')
        {
            dq[0].push_back(i);
        }
    }
	
    //각 턴에서 최선의 수를 제거
    for (int i = 0; i < K; i++)
    {
        //핑크빈 차례
        if (!dq[1].empty())
            dq[1].pop_front();
        else
            dq[0].pop_front();

        //블랙빈 차례
        if (!dq[0].empty())
            dq[0].pop_front();
        else
            dq[1].pop_back();
    }

	//먼저 입력된 순서대로 값 출력
    while (!dq[0].empty() || !dq[1].empty())
    {
        if (dq[0].empty())
        {
            cout << 1;
            dq[1].pop_front();
            continue;
        }
        else if(dq[1].empty())
        {
            cout << 0;
            dq[0].pop_front();
            continue;
        }

        if (dq[0].front() < dq[1].front())
        {
            cout << 0;
            dq[0].pop_front();
        }
        else
        {
            cout << 1;
            dq[1].pop_front();
        }
    }

    return 0;
}

출저

https://www.biko.kr/problem/4691