준표의 조약돌
문제 해석
까만색 조약돌을 B개 이하로 줍고, 하얀색 조약돌은 W개 이상 줍는 경우를 만족하는 가장 긴 구간을 구하는 문제입니다.
설계(10)
투 포인터 알고리즘을 사용하는 문제입니다.
까만색 돌이 B개 이하인지 아닌지로 나누어, 각각 e,s를 증가시켜줍니다.
그 후, 까만색과 하얀색의 조약돌 개수를 카운트하여 조건을 만족할 경우 최대 길이를 갱신합니다.
구현(10)
코드
#include <iostream>
using namespace std;
#define MAXN 300000
char arr[MAXN];
int N,B,W;
int main(){
ios::sync_with_stdio(false);
cin.tie(0);
cin >> N >> B >> W;
for (int i = 0 ; i <N; i++){
char tmp;
cin >> tmp;
arr[i] = tmp;
}
int s = 0;
int e = 0;
int ans = 0;
int b_cnt = 0 ;
int w_cnt = 0;
while (s < N){
if (e <N && b_cnt<=B){
if (arr[e] == 'W') w_cnt++;
else b_cnt++;
e++;
if (b_cnt <= B && w_cnt>=W && ans < w_cnt+b_cnt){
ans = w_cnt+b_cnt;
}
}
else{
if (arr[s] == 'W') w_cnt--;
else b_cnt--;
s++;
}
}
cout << ans <<"\n";
return 0;
}
디버깅
조건을 확인할 때, 까만색 조약돌의 개수가 B개 이하인지 체크하지 않는 실수를 하였습니다.
제출결과
8 ms
마무리
투포인터 알고리즘을 활용하는 문제였습니다.