[BOJ] 바이너리 문자열 토글

greedy? sweeping?

2024-10-05

바이너리 문자열 토글 #

TimeLimit	MemoryLimit	Condition	TAG
2s	128MB	(1 ≤ N, U ≤ 100,000)	greedy, sweeping

길이가 N이고 모든 문자가 0인 바이너리 문자열 S0이 있다. 이 문자열에 변경 연산을 총 U번 할 것이고, 변경 연산이 끝난면 다른 문자열로 바뀌게 된다. i번째 연산은 Si-1을 Si로 바꾸는 연산이다. 따라서, U번의 변경 연산이 모두 끝나게 되면 문자열은 SU가 된다.

변경 연산은 (Li, Ri)와 같은 형태이다. 연산은 구간 [Li, Ri] (양 끝도 포함)에 속하는 모든 1을 0으로 바꾸고, 0을 1로 바꾸는 것이다.

모든 연산이 끝나게 되면, S0, S1, …, SU를 구할 수 있게 된다. 이 U+1개의 바이너리 문자열 중에서 사전 순으로 가장 뒤에 오는 것을 구하는 프로그램을 작성하시오.

0->1 / 1->0 이다 그러면 뭐가 생각날까요? 바로 XOR이 떠오르죠? 일단 이걸 구현하고, 그걸 문제에 적용시키면서 그냥 사전순으로 업데이트하면 뙇 문제가 풀립니다.

(그냥 누적으로 xor 쌓은 다음에 각 단계 문자열 비교하고 최대 문자열 비교해서 업데이트하는 방법으로 구현하여 AC 맞음)

정답 코드

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

const int MAX_N = 100001;

int N, U;
int xr[MAX_N];
string result(MAX_N, '0');

int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);

    cin >> N >> U;

    
    vector<pair<int, int>> op(U);
    for (int i = 0; i < U; i++) {
        cin >> op[i].first >> op[i].second;
        op[i].first--;
    }

    for (pair<int, int> op : op) {
        xr[op.first] ^= 1;
        xr[op.second] ^= 1;
    }

    int current = 0;
    for (int i = 0; i < N; i++) {
        current ^= xr[i];
        result[i] = current + '0';
    }

    string max_string = result;
    for (int i = U - 1; i >= 0; i--) {
        for (int j = op[i].first; j < op[i].second; j++)
            result[j] = (result[j] - '0') ? '0' : '1';
        max_string = max(max_string, result);
    }

    for(int i = 0; i < N; i++) cout << max_string[i];

    return 0;
}