BOJ 31421 : 호떡 뒤집기

• 문제 링크 : boj.kr/31421
• 난이도 : G1
• 태그 : 애드혹, 해 구성하기

31421번: 호떡 뒤집기

---

코드

#include <bits/stdc++.h>

#define all(x) (x).begin(), (x).end()

#define INF 0x7FFFFFFF

using namespace std;

using ll = long long;
using ld = long double;
using pii = pair<int,int>;
using pll = pair<ll, ll>;

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

    int n;
    cin >> n;
    string s;
    cin >> s;
    if(s[n-1] == 'B') {
        vector<pii> arr;
        for(int i = 0; i < n; i++) {
            if(s[i] == 'W') {
                arr.push_back({i, -1});
                while(i < n && s[i] == 'W') {
                    i++;
                }
                arr[arr.size()-1].second = i;
            }
        }
        if(arr.size() == 0) {
            cout << -1;
        }
        else if(arr[0].first == 0) {
            if(arr.size() == 1) {
                cout << -1;
            }
            else {
                cout << arr.size() * 2 - 1 << "\n";
                cout << arr[1].second << "\n";
                cout << arr[0].second << "\n";
                cout << arr[1].first << "\n";
                for(int i = arr.size() - 1; i > 1; i--) {
                    cout << arr[i].second << "\n";
                    cout << arr[i].first << "\n";
                }
            }
        }
        else {
            cout << arr.size() * 2 << "\n";
            cout << arr[0].second << "\n";
            cout << arr[0].first << "\n";

            for(int i = arr.size() - 1; i > 0; i--) {
                cout << arr[i].second << "\n";
                cout << arr[i].first << "\n";
            }
        }
    }
    else {
        vector<pii> arr;
        for(int i = 0; i < n; i++) {
            if(s[i] == 'B') {
                arr.push_back({i, -1});
                while(i < n && s[i] == 'B') {
                    i++;
                }
                arr[arr.size()-1].second = i;
            }
        }
        if(arr.size() == 0) {
            cout << 0;
        }
        else {
            if(arr[0].first == 0) {
                cout << arr.size() * 2 - 1 << "\n";
                cout << arr[0].second << "\n";
            }
            else {
                cout << arr.size() * 2 << "\n";
                cout << arr[0].first << "\n";
                cout << arr[0].second << "\n";
            }
            for(int i = 1; i < arr.size(); i++) {
                cout << arr[i].first << "\n";
                cout << arr[i].second << "\n";
            }
        }
    }
    return 0;
}

---

풀이

케이스 별로 나눠서 풀었다.

 

한 번의 작업을 수행했을 때, 양 쪽의 호떡의 색이 달라진다는 것을 발견한다면 더 나은 풀이를 찾을 수 있다.