백준 1391 - 종이접기

2024-01-07

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

문제

지훈이의 취미는 종이 접기이다. 지훈이는 직사각형의 종이에 정사각형 모양안에 N이하의 정수가 한 번씩 쓰여 있는 종이를 가지고 왔다. 아래 그림과 같이 정사각형을 이어서 붙인 모양이다. 지훈이는 이 종이를 접어서 위에서부터 차례대로 1, 2, 3, …, N까지의 번호가 있는 정사각형이 오게 하는 것이다.

picture1

예를 들어 3, 1, 5, 2, 4의 번호가 있는 직사각형 종이가 주어졌으면, 4와 5의 경계선을 접고, 1과 3의 경계선을 접고, 2와 4의 경계선을 접으면 위에서부터 차례대로 1, 2, 3, 4, 5의 순서로 종이가 놓이게 된다.

picture2

종이에 쓰여 있는 정수 주어졌을 때, 그것을 접어서 위에서부터 차례대로 1, 2, 3, …, N의 순서로 접을 수 있는지 없는지를 구하는 프로그램을 작성하시오.

입력

첫 줄에는 입력으로 들어오는 데이터의 개수 T가 주어진다. 데이터는 각각 2줄로 이루어져 있다. 첫 줄에는 종이의 길이 N이 주어진다. 둘째 줄에는 종이에 쓰여 있는 정수가 공백을 사이에 두고 차례대로 주어진다. T는 10보다 작거나 같은 자연수이다. N은 2,000보다 작거나 같은 자연수이다.

출력

각각의 데이터에 대해 종이를 위에서부터 차례대로 1, 2, 3, …, N 순서대로 접을 수 있으면 YES를 접을 수 없으면 NO를 출력한다.

풀이

가능한 경우 접었을 때 결과를 그려보자. 다음은 예제인 3 1 5 4 2에 대한 결과이다.

┌─1──┐ 
│─2─┐│ 
└─3─││ 
┌─4─┘│ 
└─5──┘

위와 같이 1부터 순서대로 쌓고 이웃한 숫자끼리 이으면 접은 결과를 확인할 수 있다.

불가능한 경우 이와 같은 방법으로 그려보자. 다음은 예제 1 3 2 4에 대한 결과이다.

   ┌─1─ 
┌┼─2─┐ 
│└─3─┘ 
└──4─

1-3을 이은 선과 2-4를 이은 선이 겹치기 때문에 2가 적힌 종이와 4가 적힌 종이를 이을 수 없다.

즉, 1부터 순서대로 쌓고 이웃한 숫자까리 이은 선 중 교차하는 것이 있는지 판별하면 된다. 다만 종이의 왼쪽과 오른쪽을 번갈아 이어야 하므로, 홀수 번째 수와 짝수 번째 수를 분리하여 각각 겹치는 것이 있는지 확인하면 된다.

여러 선 중 겹치는 것이 존재하는지 판단할 때 스위핑 알고리즘을 사용할 수 있다. 선을 순회하는 것이 아니라 숫자를 선회하는 것이다.

가장 최근에 열린 선이 닫히기 전에 다른 선이 닫히면 교차하는 것이므로, 선이 교차하지 않으려면 항상 가장 최근에 열린 선분이 닫혀야 한다. 스택을 이용하여 풀 수 있다.

선의 정보를 저장하기 위해 odd[]와 even[]을 사용했으며, i 번째 선이 $s < e$에 대해 $s$에서 열리고 $e$에서 닫히면 odd[s] = -i, odd[e] = i와 같이 저장하도록 하였다.

for문으로 숫자를 순회하며 odd[]가 음수면 스택에 추가하고, 양수면 스택의 첫 값과 비교하는 식으로 구현하였다.

코드

#include <bits/stdc++.h>
using namespace std;
int main(){
    int T; cin >> T;
    for (int _T = 0; _T < T; _T++){
        int n; cin >> n;
        int curri, previ; cin >> previ;
        int odd[2005], even[2005];

        for (int i = 0; i < n + 2; i++){
            odd[i] = 5000; even[i] = 5000; // 초기화
        }

        for (int i = 1; i < n; i++){
            cin >> curri;

            if (i % 2 == 0){
                even[max(previ, curri)] = i;
                even[min(previ, curri)] = -i;
            }
            else{
                odd[max(previ, curri)] = i;
                odd[min(previ, curri)] = -i;
            }

            previ = curri;
        }
        
        deque<int> d1, d2;
        bool imp = false;

        for (int i = 0; i < n + 2; i++){
            if (odd[i] > 0 && odd[i] < 2005){
                if (d1.front() + odd[i] != 0){
                    cout << "NO\n";
                    imp = true;
                    break;
                }
                d1.pop_front();
            }
            else if (odd[i] < 0){
                d1.push_front(odd[i]);
            }

            if (even[i] > 0 && even[i] < 2005){
                if (d2.front() + even[i] != 0){
                    cout << "NO\n";
                    imp = true;
                    break;
                }
                d2.pop_front();
            }
            else if (even[i] < 0){
                d2.push_front(even[i]);
            }
        }
        if (!imp) cout << "YES\n";
    }
}

여담

deque 썼다.