백준 14677: 병약한 윤호

문제 조건

---

1. 약을 맨 앞 또는 맨 뒤에서만 꺼내 먹을 수 있다.
2. 전체 3N개의 약을 모두 먹을 수 있는지 확인해야한다.
3. 만약 3N개의 약을 모두 먹을 수 없다면, 최대 몇 개까지 연속적으로 먹을 수 있는지를 구해야 한다.

---

 

문제의 N범위가 적당함으로 BFS완전 탐색을 이용해 해결할 수 있다. ch[x][y] = 배열의 구간 [x, y]가 방문되었는지 여부를 체크하는 변수로 두고 약의 앞뒤에 두개의 포인터를 queue에 집어넣어 탐색해가며 구하면 된다.

 

• 큐에서 상태를 꺼내고, 현재까지 먹은 약의 개수를 최대값으로 갱신.
• 현재 상태에서 시작 인덱스 st의 약과 끝 인덱스 ed의 약을 검사.
  • arr[st]가 ct % 3와 같으면(현재 먹어야하는 약과 맨 앞의 약이 같다면), 시작 인덱스를 오른쪽으로 이동하여 새로운 구간 [st+1, ed]을 큐에 추가.
  • arr[ed]가 ct % 3와 같으면(현재 먹어야하는 약과 맨 끝의 약이 같다면), 끝 인덱스를 왼쪽으로 이동하여 새로운 구간 [st, ed-1]을 큐에 추가.
• 방문하지 않은 구간만 큐에 추가.

 

---

소스 코드

#include <stdio.h>
#include <algorithm>
#include <queue>

using namespace std;

int n;
char s[1510];
int ch[1510][1510];
int arr[1510];

struct dat{
    int x, y, cnt;
};

int main()
{
    int i;
    scanf("%d", &n);
    scanf("%s", s);
    for(i=0;i<n * 3;i++) {
        if(s[i] == 'B') arr[i] = 0;
        else if(s[i] == 'L') arr[i] = 1;
        else arr[i] = 2;
        //printf("%d ", arr[i]);
    }
    //printf("\n");
    queue <dat> q;
    q.push({0, n * 3 - 1, 0});
    ch[0][n * 3-1] = 1;
    int ans = 0;
    while(!q.empty()) {
        int ct = q.front().cnt;
        int st = q.front().x, ed = q.front().y;
        //printf("%d %d %d\n", st, ed, ct);
        q.pop();
        if(ct > ans) ans = ct;
        if(arr[st] == ct % 3 && st <= ed) {
            if(ch[st + 1][ed] == 0) {
                ch[st + 1][ed] = 1;
                q.push({st + 1, ed, ct + 1});
            }
        }
        if(arr[ed] == ct % 3 && st <= ed) {
            if(ch[st][ed - 1] == 0) {
                ch[st][ed - 1] = 1;
                q.push({st, ed - 1, ct + 1});
            }
        }
    }
    printf("%d", ans);
    return 0;
}