BOJ 14677:: 병약한 윤호

현재까지 왼쪽에서 $l$개를 먹었고 오른쪽에서 $r$개를 먹었다고 하여 약 봉투의 상태를 $(l,r)$로 나타낼 수 있습니다. 따라서 BFS로 $(0,0)$에서 출발해 어디까지 갈 수 있는지 보면 되죠.

#include<cstdio>
#include<queue>
#include<utility>

using namespace std;

typedef pair<int, int> Pint;

int n;
char pill[1501];
queue<Pint> q;
bool visited[1500][1500];

int max_pill(void) {
    int time = 0; // 0: breakfast, 1: lunch, 2: dinner
    char s[] = "BLD";

    q.push(Pint(0, 0));
    visited[0][0] = true;

    int lv = -1, l, r;
    while (!q.empty()) {
        int sz = q.size();
        while (sz--) {
            l = q.front().first;
            r = q.front().second;
            q.pop();

            if (l + r < 3*n) {
                if (pill[l] == s[time] && !visited[l+1][r]) {
                    q.push(Pint(l+1, r));
                    visited[l+1][r] = true;
                }
                if (pill[3*n-1-r] == s[time] && !visited[l][r+1]) {
                    q.push(Pint(l, r+1));
                    visited[l][r+1] = true;
                }
            }
        }
        lv++;
        time = (time+1) % 3;
    }

    return lv;
}

int main(void) {
    scanf("%d %s", &n, pill);
    printf("%d", max_pill());
    return 0;
}