백준 23878 / C++

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

23878번: Lonely Photo

 

[ 풀이 ] 

아이디어는 쉽습니다. 연속된 G끼리, H끼리 묶어서 개수를 구해줍니다. 우선 연속된 G를 기준으로 세봅시다. 

우선 G,H의 길이가 충분하다면 G의 양끝에서 그 옆에 있는 H의 길이-1 만큼 G가 1개인

문자열을 만들 수 있습니다. 

G의 길이가 2이상이면 위와 같이 만들어지는게 전부입니다. 반면 G의 길이가 1인 경우엔 위 경우 말고

한가지 케이스가 더 생깁니다. 바로 양끝에서 골라주는 경우입니다. 이 부분을 유의해서 구현해주면 됩니다.

구현이 좀 귀찮은 문제입니다. 

 

[ Code ]

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
ll n, cnt1 = 0, cnt2 = 0;
vector<ll>g, h, L, R;

int main() {
    ios::sync_with_stdio(0), cin.tie(0);
    cin >> n;
    string s; cin >> s;
    char prev = '!';
    // vector g, h에 연속된 문자열 길이를 저장
    for (int i = 0; i < n; i++) {
        if (s[i] == 'G') {
            if (cnt2) h.push_back(cnt2);
            cnt1++;
            if (prev != 'G') cnt2 = 0;
            prev = 'G';
            if (i == n - 1) g.push_back(cnt1);
        }
        else {
            if (cnt1) g.push_back(cnt1);
            cnt2++;
            if (prev != 'H') cnt1 = 0;
            prev = 'H';
            if (i == n - 1) h.push_back(cnt2);
        }
    }
    // 항상 시작하는 문자가 L이 되게 만들자. 
    if (s[0] == 'G') L = g, R = h;
    else L = h, R = g;
    // out of bound 방지
    L.resize(n);
    R.resize(n);
    ll ans = 0;

    // 연속된 L을 기준으로 
    for (int i = 0; i < n; i++) {
        if (L[i]) {
            if (i >= 1 && R[i - 1]) ans += R[i - 1] - 1;
            if (R[i]) ans += R[i] - 1;
            if (L[i] == 1 && i && R[i - 1] && R[i]) ans += R[i - 1] * R[i];
        }
        else break;
    }

    // 연속된 R을 기준으로  
    for (int i = 0; i < n; i++) {
        if (R[i]) {
            if (L[i]) ans += L[i] - 1;
            if (L[i + 1]) ans += L[i + 1] - 1;
            if (R[i] == 1 && L[i] && L[i + 1]) ans += L[i] * L[i + 1];
        }
        else break;
    }
    cout << ans;
}