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

 

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

 

 

#문제 간단 정리

 

투 포인터 /슬라이딩 윈도우 문제

 

계속해서 조약돌을 줍다가 검은 조약돌이 초과하게 되면

슬라이딩 윈도우를 줄여주면 된다.

 

 

#문제 해결 방법

 

슬라이딩 윈도우를 사용한다고 생각하고

 

우선 기본적으로 ㅣ , r 두가지의 포인터를 설정하고

 

오른쪽으로 계속 조약돌을 r++ 하면서 주워주되

    while (r < n) {
        bw[color_map[s[r]]]++;
        r++;

 
        while (bw[0] > b ) {
            bw[color_map[s[l]]]--;
            l++;
        }

        if (bw[0] <= b && bw[1] >= w) {
            maxlength = max(maxlength, r - l);
        }
    }

 

만약 검은 조약돌의 개수가 원하는 개수보다 늘어나개 된다면

검은 조약돌이 원하는 개수 이하가 되도록 왼쪽포인터를 l++ 해서

        while (bw[0] > b ) {
            bw[color_map[s[l]]]--;
            l++;
        }

윈도우 사이즈를 줄여주도록 하자

 

 

 

#전체 코드

 

#include <iostream>
#include <string>
#include <algorithm> 
#include <map>

using namespace std;


int main() {
    int n;
    cin >> n;

    int b, w;
    cin >> b >> w;


    string s;
    cin >> s;


    int bw[2] = { 0,0 }; //0은 검정 1은 흰색
    map<char, int>color_map;
    color_map['W'] = 1;
    color_map['B'] = 0;
    int l = 0, r = 0;
    int maxlength = 0;

    while (r < n) {
        bw[color_map[s[r]]]++;
        r++;

 
        while (bw[0] > b ) {
            bw[color_map[s[l]]]--;
            l++;
        }

        if (bw[0] <= b && bw[1] >= w) {
            maxlength = max(maxlength, r - l);
        }
    }

    cout << maxlength << '\n';
    

    return 0;
}