15501)부당한 퍼즐

https://www.acmicpc.net/problem/15501

처음에 1~n에서 한 번씩 숫자가 나오는 수열이 주어진다.

1 2 3 4 5처럼 주어질 수도 있고 3 2 5 1 4처럼 특별한 규칙없이 수열이 주어질 수 있다.

처음 주어진 수열을 A라고 하자.

게임 규칙에 따라 수열 A로 가능한 연산은 뒤집기와 왼쪽, 오른쪽 밀기이다.

수열 A가 1 2 3 4 5일때 이 수열을 뒤집으면 5 4 3 2 1이다.

수열 A를 왼쪽으로 밀어내면 2 3 4 5 1, 오른쪽으로 밀어내면 5 1 2 3 4이다.

이후 수열 B가 주어지는데 수열 A로 위 연산을 통해 수열 B로 만들 수 있는 지 알아내야 한다.

뒤집기, 왼쪽, 오른쪽 밀어내기 연산을 해도 바뀌지 않는 것이 있다.

바로 수열의 순서이다.

예를들어 수열 A를 오른쪽으로 밀어내고 이를 뒤집어 만들 수 있는 수열 B들을 관찰해보자.

빨강색 화살표는 수열 A와 같은 순서를 뜻한다. 점이 시작지점이고 화살표 머리가 끝이다.

수열 A가 1 2 3 4 5일 때 빨강색 화살표는 1 2 3 4 5 순서를 따라간다.

1 2 3 4 5를 오른쪽으로 한 칸 밀어 만든 수열 B 5 1 2 3 4도 두 번째 항부터 수열 A의 순서를 따른다.

나머지도 마찬가지다.

중요한 것은 수열 B가 수열 A의 순서를 따르는 지 확인하는 일이다.

이를 위해 수열 B에서 수열 A의 시작이 어떤 항인지 알아야 하고 

수열 B가 왼쪽 방향으로 수열 A의 순서를 따르는 지 오른쪽 방향으로 수열 A의 순서를 따르는 지 알아야 한다.

만약 수열 B가 수열 A의 순서를 따르면 good puzzle이고 수열 A의 순서를 따르지 않는다면 bad puzzle이다.

#include<stdio.h>
 
typedef enum _BOOL {
    TRUE = 1, FALSE = 0
}BOOL;
typedef enum _DIRECTION {
    LEFT = -1,NONE = 0, RIGHT = 1
}DIRECTION;
 
int main() {
    int n;
    int *A, *B;
    int t;
    BOOL isFound = FALSE;
    BOOL isDifferent = FALSE;
    DIRECTION direction;
 
    scanf("%d",&n);
    A = (int *)malloc(sizeof(int)*n);
    B = (int *)malloc(sizeof(int)*n);
 
    for (int i = 0; i < n;i++) {
        scanf("%d", &A[i]);
    }
    for (int i = 0; i < n; i++) {
        scanf("%d", &B[i]);
    }
 
    for (int j = 0; j < n;j++) {
        if (A[0] == B[j]) {
            t = j;    
            break;
        }
    }
 
    if (t > 0 && B[(t - 1) % n] == A[1]) {
        direction = LEFT;
    }
    else if (t == 0 && B[n - 1] == A[1]) {
        direction = LEFT;
    }
    else if (B[(t + 1) % n] == A[1]) {
        direction = RIGHT;
    }
    else {
        direction = NONE;
    }
 
    for (int i = 0; i < n; i++) {
        if (A[i] != B[t]) {
            isDifferent = TRUE;
            break;
        }
 
        if(direction == RIGHT) t = (t + direction) % n;
        else if(t>0) t = (t + direction) % n;
        else t = n - 1;
    }
    
    if (isDifferent) printf("bad puzzle\n");
    else printf("good puzzle\n");
 
    return 0;
}