Passport Control
-
[Algo Rhythm🕺💃] BOJ 16288. Passport ControlAlgo Rhythm🕺💃/BOJ 2020. 9. 3. 10:32
📚 문제 설명 $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, ..