취미로 코딩하기

※ 글쓴이는 취미로 코딩을 익혀보는 사람이라 정확하지 않은 내용을 담고 있을 수 있다 ※

이번에 볼 문제는 백준 24979번 문제인 COW Operations이다.
문제는 아래 링크를 확인하자.

https://www.acmicpc.net/problem/24979 

모든 문자열은 맨 마지막 두 문자가 같으면 둘을 지우고, 그렇지 않다면 마지막 문자를 마지막에서 두번째 문자와 다른 문자로 바꾼 뒤 같은 두 문자를 지우는 것으로 항상 길이를 줄여나갈 수 있다.

또한, C, O, W 각 문자의 개수의 홀짝은 같은 문자를 지울 때는 전부 그대로고, 문자 하나를 다른 문자 둘로 바꿀 때는 전부 홀수면 짝수로 짝수면 홀수로 바뀌므로, C만 남아있으려면 C, O, W의 개수의 개수는 순서대로 홀짝짝 개거나 짝홀홀 개여야 한다.

prefix sum을 이용하여 Q개의 쿼리에 대하여 빠르게 계산해 문제를 해결하자.

아래는 제출한 소스코드이다.

#include <iostream>
#include <string>
using namespace std;

string s;
int C[200001];
int O[200001];
int W[200001];

int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);
	
	cin >> s;
	s = " " + s;
	int slen = s.length();
	for (int i = 1; i < slen; i++) {
		C[i] = C[i - 1], O[i] = O[i - 1], W[i] = W[i - 1];
		if (s[i] == 'C')C[i]++;
		else if (s[i] == 'O') O[i]++;
		else W[i]++;
	}

	int Q; cin >> Q;
	while (Q--) {
		int L, R; cin >> L >> R;
		L--;
		int c = C[R] - C[L], o = O[R] - O[L], w = W[R] - W[L];
		if (((c & 1) && !(o & 1) && !(w & 1)) || (!(c & 1) && (o & 1) && (w & 1))) cout << 'Y';
		else cout << 'N';
	}
}