백준 34501 (C++) Busy Beaver's Colorful Walk

최초 업로드: 2025-11-16 03:25:14

최근 수정 시간: 2025-11-16 03:27:25

게시자: rlatjwls3333

카테고리: 백준

# [Gold II] Busy Beaver's Colorful Walk

[문제 링크](https://www.acmicpc.net/problem/34501)

## 문제 설명

Busy Beaver is taking a walk on a path of colorful tiles.

The path consists of a line of $N$ tiles, each colored either red (<code>r</code>), green (<code>g</code>), blue (<code>b</code>), or yellow (<code>y</code>).

Busy Beaver's walk will follow these rules:

<ul>
	<li>The walk visits $N$ tiles, starting from any initial tile.</li>
	<li>Each move must be to a tile at most two positions away from the current tile (possibly revisiting a previously visited tile, going backwards, or staying at the same tile).</li>
</ul>

Busy Beaver will record the sequence of tile colors he visits on the walk in order. Busy Beaver is confident that he can recreate any sequence of $N$ colors on his walk.

Prove him wrong by providing any sequence of $N$ colors he can't recreate.

It can be shown that an answer always exists.

## 입력

Each test contains multiple test cases. The first line contains the number of test cases $T$ ($1 \leq T \leq 10^4$). The description of the test cases follows.

The first line of each test case contains an integer $N$ ($3 \leq N \leq 3000$) --- the number of tiles.

The second line of each test case contains a length $N$ string of characters in ('<code>r</code>', '<code>g</code>', '<code>b</code>', '<code>y</code>'), the $i$'th character denoting the color of the $i$'th tile.

It is guaranteed that the sum of $N$ across all test cases is no more than $3 \cdot 10^5$.

## 출력

For each test case, output the answer-sequence as a string of characters in ('<code>r</code>', '<code>g</code>', '<code>b</code>', '<code>y</code>').

## 풀이
문제의 핵심은 문자열의 끝으로 보내면 인접한 문자가 최대 3개이므로 최소 1개의 문자가 등장하지 않아, 그 문자를 넣어 불가능하게 만드는 것입니다.

- 첫 번째 문자부터 시작해 i-2 ~ i 위치에 어떤 문자들이 있는지 확인하고 i+1 ~ i+2에만 등장하는 문자를 출력해 오른쪽으로 이동시킵니다.
- 만약 i+1 ~ i+2에만 존재하는 문자가 없다면 등장하지 않은 문자로 점프하고, 이어 나갑니다.
  - 점프가 되는 이유는 만약 이를 만족하는 다른 경로가 존재한다면 이보다 오른쪽에서 시작했을 것이기 때문에 그 위치로 이동이 됨.
  - 만약 이를 만족하는 다른 경로가 없다면 이동에 실패하여 정답 문자열이 됨.
- 이제 남는 문자열은 제일 오른쪽 위치에서 이동할 수 없는 문자를 계속 출력하면 됩니다.

``` c++
#include<bits/stdc++.h>
using namespace std;

bool used[128];

int main() {
    ios::sync_with_stdio(0); cin.tie(0);
    int t; cin >> t;
    while(t--) {
        int n; string s; cin >> n >> s;

cout << s[0] << s[2];
 int cnt=2, idx=2;
 while(idx<n-1) {
 memset(used, 0, sizeof used);
 used[s[idx-2]]=used[s[idx-1]]=used[s[idx]]=true;
 if(idx+2<n && !used[s[idx+2]] && s[idx+1]!=s[idx+2]) {
 cout << s[idx+2];
 cnt++;
 idx+=2;
 } else if(!used[s[idx+1]]) {
 cout << s[idx+1];
 cnt++;
 idx++;
 } else {
 int next=idx;
 while(next+1<n && used[s[next]]) next++;
 if(!used[s[next]]) {
 cout << s[next];
 cnt++;
 idx=next;
 } else {
 break;
 }
 }
 }
 memset(used, 0, sizeof used);
 used[s[idx-2]]=used[s[idx-1]]=used[s[idx]]=true;
 while(cnt++<n) {
 if(!used['r']) cout << 'r';
 else if(!used['g']) cout << 'g';
 else if(!used['b']) cout << 'b';
 else cout << 'y';
 }
 cout << '\n';
 }
}
```