#738 (Div.2) B - Mocha and Red and Blue

문제 링크 => Problem - B - Codeforces

Problem - B - Codeforces

---

dp + greedy 문제이다.

 

이 문제는 'R', 'B' 가 최소한으로 연달아 나타나도록 '?' 문자를 'R', 'B' 둘 중에 하나를 채워 넣는 문제이다.

 

그래서 임의의 문자열을 s1, s2를 둬서 s1 같은 경우는 'R' => 'B' => 'R' => ... 식으로 채우도록 하고 s2 같은 경우는 s1의 문자와 반대로 'B' => 'R' => 'B' => ... 식으로 채우도록 하였다.

 

문제에서 제공된 문자열 하나를 살펴보도록 한다.

 

S = "?R???BR" 가 주어졌을때, s1, s2를 채워가는 과정을 보이도록 하면 다음과 같다.

 

S[0] = '?' => s1 = "R" , s2 = "B" 

 

S[1] = 'R' => s1 = "RR", s2 = "BR"

 

S[2] = '?' => 여기서 s1, s2 둘중에 어느 문자열이 문자가 연속으로 나타난 갯수가 최소인지를 파악하여 최소인 문자열을 동일하게 만들도록 한다.

s1 = "RR" 은 'R' 이 연속으로 1번 나타났고 s2 = "BR" 은 문자가 연속으로 나타나지 않았으므로 s1의 문자열을 s2로 변경하도록 한다. 

즉, s1 = "BR" , s2 = "BR" 로 동일해졌고 '?' 에서 s1 = "BRR", s2 = "BRB" 가 된다.

 

s[3] = '?' => s1 = "BRRB", s2 = "BRBR"

 

s[4] = '?' => s1 = "BRRBR", s2 = "BRBRB"

 

s[5] = 'B' => s1 = "BRRBRB", s2 = "BRBRBB"

 

s[6] = 'R' => s1 = "BRRBRBR", s2 = "BRBRBBR"

 

모든 과정이 마치면 마지막으로 s1, s2의 문자가 연속으로 나타난 갯수를 파악하여 적게 나타난 문자열이 답이 된다.

 

풀이 code

#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
#include <string>
#include <iostream>
#include <algorithm>
#include <queue>
#include <stack>
#include <vector>
#include <math.h>
#include <map>
#include <set>
#define INF 1000000000
#define endl '\n'
#define ll long long

using namespace std;

int find(string s) {
	int cnt = 0;
	for (int i = 0; i < s.size()-1; i++) {
		if (s[i] == s[i + 1]) cnt++;
	}
	return cnt;
}

void test() {
	int n;
	string s;
	cin >> n >> s;

	string s1 = "", s2 = "";
	
	int op = 0;
	for (int i = 0; i < s.size(); i++) {
		if (s[i] == '?') {
			s1 = s1 + (op == 0 ? 'R' : 'B');
			s2 = s2 + (op == 0 ? 'B' : 'R');
			op = (op + 1) % 2;
		}
		else {
			for (int j = i; j < s.size(); j++) {
				if (j == s.size() - 1) i = s.size() - 1;
				if (s[j] == '?') {
					i = j - 1;
					break;
				}
				s1 += s[j], s2 += s[j];
			}
			if (find(s1) > find(s2)) s1 = s2;
			else s2 = s1;
		}
	}

	if (find(s1) > find(s2)) s1 = s2;
	else s2 = s1;

	cout << s1 << endl;
}

int main()
{
	ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);

	int t;
	cin >> t;
	for (int i = 0; i < t; i++) test();

	return 0;
}