[codeforce Global Round 11]B번

codeforces.com/contest/1427/problem/B

Problem - B - Codeforces

문제 : 문자열 s가 주어지고 W는 이김,L는 진거다. 이때 연속적으로 이긴다면 +2포인트를 얻고, 진다면 +0포인트를 얻는다. 또한, 연속된 W의 문자열 중에 제일 첫번째 W는 +1 포인트만 얻는다. 그리고 m번만큼 L->W로 바꿀 수 있다. 이때 최대로 얻을 수 있는 점수를 구해라

 

해설:

m번만큼 L->W를 바꿔서 얻을 수 있는 경우의 수는 3가지다

1) W와 W 사이에 존재하는 L을 변경하였을때 => +3 포인트를 얻을 수 있다. (WLW ->WWW : +2,+1)

2) W의 뒤에 존재하는 L을 변경하였을때 => +2 포인트를 얻을 수 있다. (WLL - >WWL : +2)

3) W앞에 존재하는 L을 변경하였을때 => +1 포인트를 얻을 수 있다.(LLW->LWW : +1)

 

그럼 우리는 최대한 많은 점수를 얻기 위해선 1번 케이스부터 순차적으로 가능한 경우의 수를 확인해 보면된다.

#include<bits/stdc++.h>

using namespace std;
using ll = long long;

void solve();
bool compare(const int a, const int b);

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

	while (t--)
		solve();
}
void solve()
{
	int n, m;
	string s;
	cin >> n >> m >> s;

	vector<int> v;
	vector<pair<int, int>> x;
	//W와 W사이에 존재하는 L의 개수를 얻기위해 인덱스를 저장
	for (int i = 0; i < n; i++)
		if (s[i] == 'W')
			v.push_back(i);
	//연속된 L의 개수와 시작되는 인덱스번호 저장
	for (int i = 1; i < v.size(); i++)
		x.push_back({ v[i] - v[i - 1] - 1,v[i-1] });
	sort(x.begin(), x.end());

	//1번 케이스
	int cnt = 0;
	for (int i = 0; i < x.size(); i++)
		for (int j = 0; j < x[i].first && cnt < m; j++, cnt++)
			s[x[i].second + j + 1] = 'W';

	int i;
	//2번 케이스
	for (i = n - 1; i >= 0 && s[i] == 'L'; i--);
	i++;
	for (; i < n && cnt < m; i++, cnt++)
		s[i] = 'W';
	//3번 케이스
	for (i = 0; i < n && s[i] == 'L'; i++);
	i--;
	for (; i >= 0 && cnt < m; i--, cnt++)
		s[i] = 'W';

	//점수 계산
	int ans = 0;
	for (int i = 1; i < n; i++)
	{
		if (s[i] == 'W') {
			if (s[i - 1] == 'W')
				ans += 2;
			else
				ans += 1;
		}
	}
	ans += (s[0] == 'W') ? 1 : 0;
	cout << ans << "\n";
}