[Algo Rhythm🕺💃] BOJ 16288. Passport Control

📚 문제 설명

 

그림 G.1:   $N$ 명의 입국 승객은 $k$ 개의 여권 심사 창구 {$Q_{k}$} 중 하나를 반드시 거쳐야 한다.

 

$N$명의 입국 승객이 여권 심사를 위하여 그림 G.1 과 같이 입국 대기 줄에서 $[1, 2, … , N − 1, N]$ 순서로 기다리고 있다. 입국 승객은 준비된 $k$개의 여권 심사 창구 중 하나를 통과한 뒤 공항을 빠져나갈 수 있다.

입국할 때의 줄 선 승객의 순서를 $[1, 2, … , N − 1, N]$이라고 할 때 $k$개의 여권 심사 창구를 통과하여 입국장을 빠져나가는 순서 $[π_{1}, π_{2}, … π_{N−1}, π_{N}]$는 처음과 달라질 수 있다. $k$개 여권 심사 창구가 준비되어 있을 때, 이 입국장을 빠져나가는 순서가 가능한 순서인가를 계산해야 한다.

예를 들어 설명해보자. 만일 $N = 3, k = 2$ 라고 할 때 입국장을 빠져나가는 순서 중 $[1, 2, 3], [1, 3, 2], [2, 1, 3], [2, 3, 1], [3, 1, 2]$ 는 가능하지만 $[3, 2, 1]$ 은 불가능하다. 여러분은 입국장을 빠져나가는 순서 $[π_{1}, … , π_{N}]$ 가 입력으로 주어질 때, 이 순서가 가능하면 YES 를, 불가능하면 NO 를 출력해야 한다. 단, 특정 큐에 줄을 선 상황에서는 승객들의 순서를 임의로 바꿀 수는 없다. 그리고 각 여권 심사 창구에 준비된 큐는 $N$명 승객이 모두 들어올 정도로 충분히 크다고 가정한다.

 

입력

입력은 표준입력을 사용한다. 첫 번째 줄에는 두 개의 정수 $N$ 과 $k$ 가 주어진다. $N$ 입국 승객의 수이며 $k$는 여권 심사 창구의 수이다. 단, $2 ≤ k ≤ N ≤ 100$ 이다. 그리고 두 번째 줄에는 승객이 입국장을 빠져 나가는 순서 $[π_{1}, … , π_{N}]$가 주어진다.

 

출력

출력은 표준출력을 사용한다. 입력으로 주어진 순서 $[π_{1}, … , π_{N}]$대로 입국장을 빠져나가는 것이 가능하면 YES 를 출력하고, 아니면 NO 를 출력해야 한다.

 

🎯 어떻게 풀었나

 

 

🧐 왜 저렇게 풀었나

승객들이 대기줄에 선 순서를 각 승객의 id라고 간주하자.

그렇다면 우린 id가 작은 승객부터 심사 창구에 들어간다는 사실을 알 수 있다.

이 말은 한 심사 창구에 내가 서 있으면 내 앞 사람들은 나의 id보다 항상 작다는 뜻으로 해석될 수 있다.

따라서 이 성질을 이용해서 input으로 들어오는 입국장을 빠져나오는 순서의 가능여부를 판단하면 된다.

 

 

📖 무엇을 배웠나

간단한 성질인데 떠올리기가 쉽지 않다.😅😅