백준(BOJ) 15831번 준표의 조약돌

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

15831번: 준표의 조약돌

풀이 :

 

완전 탐색은 시간 초과가 나므로 투 포인터를 이용해서 처리하자. lo와 hi 인덱스를 0으로 둔 후

 

조건을 만족하면 범위의 최댓값을 구하는 연산을 해준다.

 

 

코드 ( C++ )

	#include <string>
	#include <iostream>
	#include <vector>
	#include <algorithm>
	using namespace std;
	int n, b, w;
	const int INF = 987654321;
	int main()
	{
	cin >> n >> b >> w;
	string s;
	cin >> s;
	int lo = 0, hi = 0;
	int bc = 0, wc = 0;
	int ans = 0;
	while (lo < n) {
	if (hi < n && s[hi++] == 'W')
	wc++;
	else
	bc++;
	if (bc <= b && wc >= w) {
	ans = max(ans, hi - lo);
	}
	else if (bc > b) {
	if (s[lo++] == 'W')
	wc--;
	else
	bc--;
	}
	}
	cout << ans << "\n";
	}

view raw .cpp hosted with ❤ by GitHub