# [Silver II] 부당한 퍼즐 [문제 링크](https://www.acmicpc.net/problem/15501) ## 문제 설명 <p>현욱은 퍼즐 게임을 굉장히 좋아한다. 어느 날 현욱은 친구로부터 간단한 플래시 퍼즐 게임을 하나 추천 받았는데, 이 퍼즐 게임은 다음과 같은 규칙을 갖고 있다.</p> <ol> <li>플레이어는 1 ~ n 까지 숫자가 한 번씩만 나타나는 수열을 하나 가지고 시작한다.</li> <li>또 다른 1 ~ n 까지 숫자가 한 번씩만 나타나는 수열이 주어졌을 때, 처음 수열을 적절히 변형해서 처음 받은 수열을 이 수열과 동일한 수열로 만들어야 한다.</li> <li>이때, 플레이어가 수열에 대해서 할 수 있는 동작은 다음 두 가지가 있다. 동작은 몇 번이라도 수행할 수 있다. <ul> <li>뒤집기 : 현재 수열을 거꾸로 뒤집는다. ex) 1 2 3 4 5 -> 5 4 3 2 1</li> <li>밀기 : 현재 수열을 왼쪽 혹은 오른쪽으로 한 칸 민다. ex) 1 2 3 4 5 -> 5 1 2 3 4</li> </ul> </li> </ol> <p>퍼즐을 풀던 현욱은 분명히 엄청 쉬운 규칙인데도 불구하고 문제가 안 풀려서, 한참을 고민하다가 다시 잘 비교해보니 정답 수열을 주어진 동작만으로는 절대 만들 수가 없는 문제였다!</p> <p>화가 난 현욱은 퍼즐 제작자에게 따지기 위해 주어진 문제가 올바른 문제인지 아닌지 확인하는 프로그램을 만들기로 결심했다. 현욱을 도와 괘씸한 퍼즐 제작자를 응징해주자.</p> ## 입력 <p>첫째 줄에 n이 주어진다(1 ≤ n ≤ 1,000,000).</p> <p>둘째 줄에 1에서 n까지의 수가 한 번만 나타나는 수열이 순서대로 주어진다.</p> <p>셋째 줄에 주어진 두 연산을 수행해서 구성할 수 있는지 확인할 1에서 n까지 수가 한 번만 나타나는 수열이 순서대로 주어진다.</p> ## 출력 <p>주어진 두 가지 연산만을 가지고 처음 수열을 결과 수열로 만들 수 있다면 good puzzle, 아니면 bad puzzle을 출력한다.</p> ## 풀이 두 연산 모두 인접한 원소를 바꾸지는 않으니, B가 A를 한 숫자를 기준으로 그대로 배치하거나, 뒤집어서 배치하는 두 상태 중 하나와 같다면 A를 B로 변환할 수 있습니다. ``` c++ #include<bits/stdc++.h> using namespace std; int n, a[1'000'000], aIdx[1'000'001], b[1'000'000]; bool chk(int idx) { bool chk1=true, chk2=true; for(int i=0;i<n;i++) { chk1 &= a[(idx+i)%n]==b[i]; chk2 &= a[(idx-i+n)%n]==b[i]; } return chk1 | chk2; } int main() { ios::sync_with_stdio(0); cin.tie(0); cin >> n; for(int i=0;i<n;i++) { cin >> a[i]; aIdx[a[i]]=i; } for(int i=0;i<n;i++) cin >> b[i]; cout << (chk(aIdx[b[0]])? "good puzzle" : "bad puzzle"); } ```