BOJ 32111 : 관광 코스

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

---

코드

#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;
    s = s + s;
    vector<int> ans(n);
    vector<int> O;
    for(int i = 0; i < n*2; i++) {
        if(s[i] == 'O') {
            O.emplace_back(i);
            ans[i%n] = 1;
        }
    }
    for(int i = 1; i < O.size(); i++) {
        int d = O[i] - O[i-1] - 1;
        if(d > 0 && d%2 == 0) {
            cout << "NO";
            return 0;
        }
        for(int j = 0; j < d; j++) {
            ans[(O[i-1]+j+1)%n] = j < d/2;
        }
    }

    cout << "YES\n";
    for(auto u : ans) {
        cout << (u ? '+' : '-');
    }

    return 0;
}

---

풀이

원형 코스이기 때문에 주어진 문자열에 두 배를 해준다.

쉽게 알 수 있는 조건부터 살펴보자. O로 표시된 곳은 반드시 +여야 한다. -로 시작할 경우 코스를 완주할 수 없다.

O는 쉽게 채웠으니 X에 대해 살펴보자.

O와 O의 사이에 X가 0 이상의 짝수개 있다면 조건을 만족하는 코스는 없다.

X로 이루어진 구간에 +를 -보다 많거나 같게 배치하면 어떤 X에서 시작하는 관광객은 코스를 완주하게 된다.

X로 이루어진 구간에 +를 -보다 적게 배치한다면 이 구간의 어떤 O에서 시작하는 관광객은 코스를 완주하지 못한다.

따라서 O와 O의 사이에 X는 홀수개가 존재해야 하고, +보다 -가 한 개 더 많게 잘 배치하면 된다. 쉽게 생각할 수 있는 방법으로는 앞쪽에 +를 배치하고 뒤쪽에 -를 배치하는 방법이 있다.