알고리즘 스터디 - 백준 16288번 : Passport Control

문제 해석

• N명의 승객이 k개의 심사 창구를 빠져나오는 순서가 가능한지 불가능한지 여부를 계산
• 가능하면 YES, 불가능하면 NO

어떤 알고리즘을 써야할까?

가정 : q1, q2가 있고 1, 2, 3이 있다고 하자
의문 : [1, 2, 3], [1, 3, 2], [2, 1, 3], [2, 3, 1], [3, 1, 2]는 가능한데 왜 [3, 2, 1]이 안될까?

[1, 2, 3] : 1(q1), 2(q2), 3(q1 or q2)
[1, 3, 2] or [2, 1, 3], [2, 3, 1] : 1(q1), 2(q2), 3(q1) 속도가 다름
[3, 1, 2] : 이 경우 1이 q1, 2도 q1, 3은 q2
[3, 2, 1] : 이 경우 2가 이상해진다. 2는 같은 줄을 설수 있지만 1보다는 뒤에 있어야 한다.

여기서 순서가 앞선 승객은 순서가 앞서지 않은 승객보다 뒤에 있으면 안된다.

이 경우 만약 거꾸로 되돌렸을 때 각 심사 창구에서의 q1 : 3, q2 : 2, 1과 같은 상황이 일어나면 안되는 것이다.

알고리즘 코드

# 승객 및 창구
N, k = map(int, input().split())

# 입국장을 빠져나가는 순서
answer = list(map(int, input().split()))

# 창구 순서 저장
graph = [[101] for _ in range(k)]

final = ""

# 각 순서를 거꾸로 해서 집어 넣음
for i in reversed(answer):
    final = "NO"
    # 항상 모든 창구에 숫자가 들어갈 때는 이전에 들어갔던 숫자보다 크면 안된다.
    for j in range(k):
        if i < graph[j][0]:
            final = "YES"
            graph[j].insert(0, i)
            break
    if final == "NO":
        break

if final == "NO":
    print("NO")
else:
    print("YES")