위 포스트는 백준 24979 - COW Operations에 대한 해설입니다.

핵심 아이디어#

아이디어1#

주어진 Operation을 해보면 아래와 같은 변환이 가능하다는 것을 알 수 있다.

• OW, WO ↔ C
• WC. CW ↔ O
• CO, OC ↔ W

양쪽으로 자유롭게 왔다갔다할 수 있다.

아이디어2#

문자의 순서를 바꿀 수 있다.

• CO ↔ OC
• WC ↔ CW
• WO ↔ OW

주어진 Operation을 해보면 문자의 순서를 바꿀 수 있다는 사실을 알 수 있다.

아이디어3#

C 하나를 남겨야 하므로 O나 W 둘 중 하나를 아예 제거해보자.
W를 제거한다고 가정하면 아이디어1에 의해 W를 전부 CO나 OC로 바꿀 수 있다.
결과적으로 C와 O로 이루어진 문자열을 얻을 수 있다.

풀이#

아이디어2와 아이디어3에 의해서 문자열을 CC...CCOO...O 꼴로 만들 수 있다.
이때 C가 홀수개이고 O가 짝수개라면 우리는 C를 만들 수 있다는 것을 알 수 있다.

C와 O의 개수는 각각 누적합을 이용해서 세어준다.

코드#

cpp
1#include <bits/stdc++.h>
2
3#define endl "\n"
4#define all(v) (v).begin(), (v).end()
5#define all1(v) (v).begin()+1, (v).end()
6#define For(i, a, b) for(int i=(a); i<(b); i++)
7#define FOR(i, a, b) for(int i=(a); i<=(b); i++)
8#define Bor(i, a, b) for(int i=(a)-1; i>=(b); i--)
9#define BOR(i, a, b) for(int i=(a); i>=(b); i--)
10#define ft first
11#define sd second
12
13using namespace std;
14using ll = long long;
15using lll = __int128_t;
16using ulll = __uint128_t;
17using ull = unsigned long long;
18using ld = long double;
19using pii = pair<int, int>;
20using pll = pair<ll, ll>;
21using ti3 = tuple<int, int, int>;
22using tl3 = tuple<ll, ll, ll>;
23
24template<typename T> using ve = vector<T>;
25template<typename T> using vve = vector<vector<T>>;
26
27template<class T> bool ckmin(T& a, const T& b) { return b < a ? a = b, 1 : 0; }
28template<class T> bool ckmax(T& a, const T& b) { return a < b ? a = b, 1 : 0; }
29
30const int INF = 987654321;
31const int INF0 = numeric_limits<int>::max();
32const ll LNF = 987654321987654321;
33const ll LNF0 = numeric_limits<ll>::max();
34
35void solve() {
36    string s; cin >> s;
37    ve<ll> csum(s.length()+1, 0), osum(s.length()+1, 0);
38    for(int i=1; i<=s.length(); i++) {
39        char c = s[i-1];
40        csum[i] = csum[i-1] + (c == 'O' ? 0:1);
41        osum[i] = osum[i-1] + (c == 'C' ? 0:1);
42    }
43
44    int q; cin >> q;
45    string ans;
46    while(q--) {
47        int l, r; cin >> l >> r;
48        ll cval = csum[r] - csum[l-1];
49        ll oval = osum[r] - osum[l-1];
50        ans += ((cval%2 == 1 and oval%2 == 0) ? "Y" : "N");
51    }
52    cout << ans << endl;
53}
54
55int main(void) {
56    ios_base::sync_with_stdio(false);
57    cin.tie(nullptr);
58    cout.tie(nullptr);
59    
60    int TC=1;
61//    cin >> TC;
62    FOR(tc, 1, TC) {
63//        cout << "Case #" << tc << ": ";
64        solve();
65    }
66
67
68    return 0;
69}

참고#

https://dong-gas.tistory.com/76