취미로 코딩하기

※ 글쓴이는 취미로 코딩을 익혀보는 사람이라 정확하지 않은 내용을 담고 있을 수 있다 ※

이번에 볼 문제는 백준 7803번 문제인 Burger, French Fries, Soft Drink이다.
문제는 아래 링크를 확인하자.

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

먼저 주어진 B, F, S의 개수가 서로 같지 않다면 당연히 세트를 나누는 것이 불가능하다. 아래에서는 전체 B, F, S의 개수가 서로 같은 상황만을 생각하자.

앞의 B, F, S의 개수가 서로 같게 끊을 수 있는 모든 위치를 먼저 구하면, 세트를 나눌 수 있는 지점은 그 부분뿐이며 그 중 $N-1$개의 지점을 고르는 것으로 모든 가능한 경우를 찾을 수 있다.

이와 같은 경우의 수는 조합과 같으므로, 파스칼의 삼각형을 구현해 문제를 해결할 수 있다. 문제의 답의 최댓값이 충분히 작아 이와 같은 방식으로도 문제를 충분히 해결할 수 있다.

아래는 제출한 소스코드이다.

#include <iostream>
#include <string>
using namespace std;

int comb[34][34];
void combinit() {
    comb[0][0] = 1;
    for (int n = 1; n < 34; n++) {
        comb[n][0] = 1;
        for (int r = 1; r < 34; r++) {
            comb[n][r] = comb[n - 1][r - 1] + comb[n - 1][r];
        }
    }
}

int N; string s;
int cnt[128];

void solve() {
    int n = 0;
    cnt['B'] = cnt['F'] = cnt['S'] = 0;
    for (auto &l:s) {
        cnt[l]++;
        if (cnt['B'] == cnt['F'] && cnt['F'] == cnt['S']) n++;
    }
    if (cnt['B'] != cnt['F'] || cnt['F'] != cnt['S']) {
        cout << "Impossible\n";
        return;
    }
    n--;

    if (comb[n][N - 1]) cout << comb[n][N - 1] << '\n';
    else cout << "Impossible\n";
}

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

    combinit();
    while (cin >> N >> s) solve();
}