fragment-header
fragment-markdown
홈
로그인
로그아웃
내 블로그
설정
로그인
백준 34501 (C++) Busy Beaver's Colorful Walk
최초 업로드: 2025-11-16 03:25:14
최근 수정 시간: 2025-11-16 03:27:25
게시자: rlatjwls3333
카테고리: 백준
조회수: 6
# [Gold II] Busy Beaver's Colorful Walk [문제 링크](https://www.acmicpc.net/problem/34501) ## 문제 설명 <p>Busy Beaver is taking a walk on a path of colorful tiles.</p> <p>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>).</p> <p>Busy Beaver's walk will follow these rules:</p> <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> <p>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.</p> <p>Prove him wrong by providing any sequence of $N$ colors he can't recreate.</p> <p>It can be shown that an answer always exists.</p> ## 입력 <p>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.</p> <p>The first line of each test case contains an integer $N$ ($3 \leq N \leq 3000$) --- the number of tiles.</p> <p>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.</p> <p>It is guaranteed that the sum of $N$ across all test cases is no more than $3 \cdot 10^5$.</p> ## 출력 <p>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>').</p> ## 풀이 문제의 핵심은 문자열의 끝으로 보내면 인접한 문자가 최대 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'; } } ```