492 words
2 minutes
[BOJ] 바이너리 문자열 토글
바이너리 문자열 토글
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;
}
[BOJ] 바이너리 문자열 토글
https://compy07.github.io/Blog/posts/boj/14893/