[백준] 15831번 : 준표의 조약돌 (C++)

15831번 : 준표의 조약돌

---

문제)

 

 

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

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

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

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

 

 

 

입력 :

첫 줄에 조약돌의 총 개수 N, 준표가 원하는 검은 조약돌의 최대개수 B와 하얀 조약돌의 최소개수 W가 주어진다. 둘째 줄에는 N개의 조약돌의 정보가 한 줄로 주어진다. i번째 문자가 B라면 i번 조약돌은 검은색이고, W라면 흰색이다.

 

 

 

출력 :

준표와 미미가 걷게 될 가장 긴 구간의 길이를 한 줄에 출력한다. 준표가 원하는 조건에 맞는 구간이 없다면 0을 출력한다.

 

 

 

 

풀이)

 

// 15831. 준표의 조약돌
#include <iostream>
#include <string>
 
using namespace std;
 
int main()
{
    int n, b, w;
    cin >> n >> b >> w;
 
    string road;
    cin >> road;
 
    // 주어진 길의 길이
    int iLen = road.length();
 
    int s = 0;
    int e = 0;
 
    // 첫번째 조약돌이 무엇이냐에 따라 값을 조정한다.
    int cntBlack = road[0] == 'W' ? 0 : 1;
    int cntWhite = road[0] == 'W' ? 1 : 0;
 
    // 답이 들어갈 가장 긴 구간의 길이
    int ans = 0;
 
    // e가 길의 마지막에 도달할 때까지
    while (e < iLen)
    {
        // 두 조건을 모두 만족할 경우, 제일 큰 값을 ans에 저장한다.
        if (cntWhite >= w && cntBlack <= b) ans = max(ans, e - s + 1);
 
        // 주운 까만색 조약돌이 b보다 작다면 구간을 늘린다.
        if (cntBlack <= b)
        {
            e++;
            if (road[e] == 'B') cntBlack++;
            else if (road[e] == 'W') cntWhite++;
        }
        // 주운 까만색 조약돌이 b보다 크다면, s부터의 구간에서는
        // 더 이상 긴 구간이 나올 수 없으므로
        else if (cntBlack > b)
        {
            if (road[s] == 'B') cntBlack--;
            else if (road[s] == 'W') cntWhite--;
            s++;
        }
    }
 
    cout << ans;
 
    return 0;
}
 

---

출처 : https://www.acmicpc.net/problem/15831 

15831번: 준표의 조약돌