[BOJ] #15831 준표의 조약돌

시간 제한	메모리 제한	정답 비율
1 초	512 MB	39.924 %

15831번: 준표의 조약돌

 

문제

준표는 오랜만에 미미와 함께 산책을 나왔다. 산책로에는 일렬로 검은색과 흰색 조약돌이 놓여 있다. 총 N개의 조약돌은 1번부터 N번까지 차례로 번호가 붙여져 있다. 준표는 이 조약돌을 주워 집에 장식하려고 한다.

준표는 임의의 지점에서 산책을 시작하고, 원하는 지점에서 산책로를 빠져나와 집으로 돌아간다. 이때 준표는 산책한 구간에 있는 모든 조약돌을 줍는다. 미미의 건강을 위해 준표는 조금이라도 더 긴 구간을 산책하고 싶다. 하지만 준표에게는 확고한 취향이 있어, 아래 조건을 만족하는 구간만을 산책할 수 있다.

1. 준표는 까만색을 싫어한다. 그래서 까만색 조약돌은 B개 이하로 줍고 싶다.
2. 준표는 미미와 같은 흰색을 좋아한다. 그래서 흰색 조약돌은 W개 이상 줍고 싶다.

만약 위 조건을 만족하는 구간이 없다면 준표는 바로 집으로 돌아간다. 이때 준표와 미미가 산책할 수 있는 구간 중 가장 긴 구간의 길이를 구해보자.

해결

key point, 투포인터.

1. 시작점을 가리키는 포인터 l, 끝점을 가리키는 포인터 r을 둔다.
2. r을 한 칸씩 늘려가면서 조약돌을 줍는다.
3. 주운 까만색 조약돌이 B개 이상이 되면 l 위치에 있는 조약돌을 버린다.
4. 준표가 원하는 조건(까만색 조약돌 B개 이하, 흰색 조약돌 W개 이상)을 만족하면 그 때의 l부터 r까지의 길이를 ans와 비교하여 더 큰 값으로 갱신한다.
5. 포인터 r이 n 이전까지만 보고 나면 반복문을 종료한다. r이 n에 도달한 이후로부터는 l이 증가되어 결국 더 작은 길이에 해당하는 값들을 보게 되므로 더 이상 보지 않아도 된다. 
6. 가장 긴 구간의 길이를 출력하면서 프로그램을 종료한다.

 

코드

메모리	시간
2276 KB	20 ms

#include <iostream>
int n, black, white, ans;
char arr[300005];
int main() {
    scanf("%d %d %d", &n, &black, &white);
    for (int i = 1; i <= n; i++) {
        scanf(" %c", &arr[i]);
    }
    int l = 1, r = 0, b = 0, w = 0, len = 0;
    // 조건 확인
    while (r < n) {
        if (b > black) {
            if (arr[l] == 'W')    w--;
            else b--;
            l++; len--;
        }
        else {
            r++; len++;
            if (arr[r] == 'W')    w++;
            else b++;
        }
 
        if (w >= white && b <= black) {
            ans = len > ans ? len : ans;
        }
    }
    printf("%d", ans);
    return 0;
}