종이를 접는 과정을 시뮬레이션하는 것이 너무 어려워서 종이접기의 결과를 어떻게 단순히 표현할 수 있을지 생각하게 되었습니다.

완벽하게 접힌 ($1$부터 $N$까지 순서대로 나열된) 종이는 위쪽에서 바라보았을 때 각 숫자마다 왼쪽, 오른쪽, 혹은 둘 모두의 접힌 면을 가지고 있습니다.

접힌 면으로 연결된 숫자들을 접힌 면의 방향을 고려하여 선으로 이으면 두 가지 규칙을 발견할 수 있습니다.

  1. 연속한 숫자가 같은 편의 선을 가질 수 없다.

예를 들어 1-2가 오른쪽 접힌 면을 가지고, 2-3이 다시 오른쪽으로 접힌 면을 가지는 상황은 발생할 수 없습니다. (다시 강조하자면 위쪽에서 바라보았을 때 기준입니다.)

  1. 선은 서로 겹칠 수 없다.

1-3이 오른쪽으로 접힌 면을 가진 동시에 2-4가 오른쪽으로 접힐 수는 없습니다.

2번 규칙을 잘 살펴보면, 올바른 괄호 문자열을 판단하되 각 괄호에 고유한 값이 부여되어 있는 문제임을 알 수 있습니다.

각 수마다 2개의 열린 괄호와 닫힌 괄호를 생성하므로 괄호의 총 개수는 $2N$개.

스택을 사용하면 이 문제를 $O(N)$ 시간에 풀 수 있습니다.

이제 초기 상태를 결과로 어떻게 바꿀 수 있을지 생각해야 합니다.

선은 접힌 면을 나타내므로 인접한 수끼리는 서로 선으로 연결되어야 합니다.

그런데 1번 규칙에 의해 선은 왼쪽과 오른쪽을 번갈아가며 그어져야 합니다.

그 다음 선과 이어진 숫자를 기준으로 정렬하면 완벽하게 접힌 상태로 변하고, 이때 괄호의 올바름을 판단하면 문제를 해결할 수 있습니다.

코드
fn check_interleave(list: &[u32]) -> bool {
    let mut paren = Vec::with_capacity(list.len());
    let mut ident = 0;
    for i in (1..list.len()).step_by(2) {
        let mut open = list[i - 1];
        let mut close = list[i];
        if open > close {
            std::mem::swap(&mut open, &mut close);
        }
        paren.push((open, false, ident));
        paren.push((close, true, ident));
        ident += 1;
    }
    paren.sort_unstable();
    let mut stack = Vec::with_capacity(paren.len() >> 1);
    for &(_, is_close, ident) in &paren {
        if is_close {
            if stack.pop().map_or(true, |top| top != ident) {
                return false;
            }
        } else {
            stack.push(ident);
        }
    }
    true
}

fn solve(paper: &[u32]) -> bool {
    check_interleave(paper) && check_interleave(&paper[1..])
}