BOJ 28034 - FEB 링크
(2024.03.19 기준 G2)

문제

B, E, F로 이루어진 문자열 $S$가 주어진다. F는 B나 E 둘 중 하나이다.

$S$에서 BB, EE가 나타나는 횟수를 excitement level이라고 할 때, 가능한 모든 excitement level을 출력

알고리즘

관찰력을 요구하는 애드혹 문제

풀이

공식 풀이를 참고하자.

• BFFB : BBBB 3, BBEB 1, BEBB 1, BEEB 1
• BFFFB : BBBBB 4, BBBEB 2, BBEBB 2, BBEEB 2, BEBBB 2, BEBEB 0, BEEBB 2, BEEEB 2

F...F를 덮는 양쪽 문자가 동일할 때에는 F의 개수가 $n$이라면, $n+1$, $n-1$, $\dots$ 임을 알 수 있다.
즉, $n$이 홀수이면 최소 $0$, 짝수이면 최소 $1$이며, 최대는 $n+1$이다.

• BFFE : BBBE 2, BBEE 2, BEBE 0, BEEE 2
• BFFFE : BBBBE 3, BBBEE 3, BBEBE 1, BBEEE 3, BEBBE 1, BEBEE 1, BEEBE 1, BEEEE 3

F...F를 덮는 양쪽 문자가 동일하지 않을 때에는 F의 개수가 $n$이라면, $n$, $n-2$, $\dots$ 임을 알 수 있다.
즉, $n$이 홀수이면 최소 $1$, 짝수이면 최소 $0$이며, 최대는 $n$이다.

위 과정을 F가 아닌 두 문자 사이마다 확인하면 된다.

단, 엣지 케이스가 하나 있다. 바로 맨 앞이나 맨 뒤에 F가 있는 것.

• FB : BB 1, EB 0
• FFB : BBB 2, BEB 0, EBB 1, EEB 1

F...F가 맨 앞이나 맨 뒤에 있고 F의 개수가 $n$이라면, $n$, $n-1$, $\dots$ 임을 알 수 있다.
즉, 최소는 $0$, 최대는 $n$이고 $1$씩 증가하게 된다.
그래서 이 케이스를 만족한다면 $1$씩 증가, 아니면 $2$씩 증가하게 해서 출력하면 된다.

코드

• C++

#include <bits/stdc++.h>
using namespace std;

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

    int N; cin >> N;
    string S; cin >> S;

    vector<int> p;
    for (int i = 0; i < N; i++) if (S[i] != 'F') p.push_back(i);

    // F만 있으면 0, 1, ..., N-1만 가능하다.
    if (!p.size()){
        cout << N << '\n';
        for (int i = 0; i < N; i++) cout << i << '\n';
        return 0;
    }

    // 인접한 두 위치 사이를 확인해서 최소와 최대를 갱신
    int mn = 0, mx = 0;
    for (int i = 0, sz = p.size(); i < sz - 1; i++){

        // B F ... F B
        // 끝 자리가 같고 F의 개수가 홀수이면 최소 0, F의 개수가 짝수이면 최소 1
        // 최대는 F의 개수 + 1
        if (S[p[i]] == S[p[i + 1]]){
            if (!((p[i + 1] - p[i] - 1) & 1)) ++mn;
            mx += p[i + 1] - p[i];
        }

        // B F ... F E 
        // 끝 자리가 다르고 F의 개수가 홀수이면 최소 1, F가 짝수이면 최소 0
        // 최대는 F의 개수
        else{
            if ((p[i + 1] - p[i] - 1) & 1) ++mn;
            mx += p[i + 1] - p[i] - 1;
        }
    }

    vector<int> ans;

    // F ... F B or B F ... F
    // 양 끝에 F가 있으면 그 F의 개수만큼 최대는 커지며 최소부터 최대까지 1씩 늘어난다.
    if (p[0] || p.back() < N - 1){
        mx += p[0] + N - 1 - p.back();
        for (int i = mn; i <= mx; i++) ans.push_back(i);
    }

    // 아니면 최소부터 최대까지 2씩 늘어난다.
    else
        for (int i = mn; i <= mx; i += 2) ans.push_back(i);

    cout << ans.size() << '\n';
    for (int i: ans) cout << i << '\n';
}

• Python

import sys; input = sys.stdin.readline

N = int(input())
S = input().strip()

p = []
for i in range(N):
    if S[i] != 'F':
        p.append(i)

# F만 있으면 0, 1, ..., N-1만 가능하다.
if not p:
    print(N)
    for i in range(N):
        print(i)
    exit()

# 인접한 두 위치 사이를 확인해서 최소와 최대를 갱신
mn = mx = 0
for i in range(len(p) - 1):

    # B F ... F B
    # 끝 자리가 같고 F의 개수가 홀수이면 최소 0, F의 개수가 짝수이면 최소 1
    # 최대는 F의 개수 + 1
    if S[p[i]] == S[p[i + 1]]:
        if not (p[i + 1] - p[i] - 1) & 1:
            mn += 1
        mx += p[i + 1] - p[i]

    # B F ... F E 
    # 끝 자리가 다르고 F의 개수가 홀수이면 최소 1, F가 짝수이면 최소 0
    # 최대는 F의 개수
    else:
        if (p[i + 1] - p[i] - 1) & 1:
            mn += 1
        mx += p[i + 1] - p[i] - 1

ans = []

# F ... F B or B F ... F
# 양 끝에 F가 있으면 그 F의 개수만큼 최대는 커지며 최소부터 최대까지 1씩 늘어난다.
if p[0] or p[-1] < N - 1:
    mx += p[0] + N - 1 - p[-1]
    for i in range(mn, mx + 1):
        ans.append(i)

# 아니면 최소부터 최대까지 2씩 늘어난다.
else:
    for i in range(mn, mx + 1, 2):
        ans.append(i)

print(len(ans))
for i in ans:
    print(i)