문제 바로가기

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

문제 소개 및 재정의

<입장 기준>
입장은 티켓 번호 순서대로 이루어졌다.
주최 측은 번호표 순서대로만 통과할 수 있는 입구를 만들어 두었지만,
줄에서는 마구잡이로 사람들이 기다리고 있다.
대기 공간을 이용하여 입장이 원활히 이루어지도록 하려고 한다.
콘서트장에 사람들이 제대로 들어갈 수 있는지 확인해보자.
<이동 방식>
사람들은 현재 5명씩 N 줄을 서 있고, 첫 번째 줄 맨 앞사람만 이동이 가능하다.
이 사람은 콘서트장으로 입장할 수도 있고 대기 공간에서 다시 기다릴 수도 있다.
한 줄의 사람이 다 이동했다면 그다음 줄의 사람들이 이동한다.
대기 공간에는 한 줄로만 설 수 있는 공간이 있으며, 마지막에 들어온 사람부터 나갈 수 있다.
나갈 경우 바로 입장해야 하고, 다시 줄로 돌아갈 수는 없다.
<순서 기준>
티켓은 A-123과 같이 한 개의 대문자 알파벳과 '-', 1000 미만의 자연수의 조합으로 이뤄어져 있다.
만약 수가 7이라면 A-7과 같이 주어진다.
티켓의 순서는 알파벳이 빠른 티켓이 빠르며, 동일하다면 더 적은 수가 더 빠르다.
티켓 번호는 중복되게 주어지지 않는다.
<예시와 실제문제.>
위의 예시를 예로 들면 다음과 같이 모든 사람들이 입장할 수 있다.
그림과는 달리 대기 공간에는 무한히 많은 사람들이 들어올 수 있다는 것에 주의하여야 한다.

문제 패턴

어떻게 풀까? - 시뮬레이션

포인트

답이 정해져 있다.
티켓을 정렬해서 정답을 만들어두고,
규칙에 맞게 최적화된 시물레이션 알고리즘을 돌려서, 정답과 다른 결과가 나오면 오답으로 처리한다.
이지선다를 반복하면서 최종까지 갔을때 정답이 나올것으로 기대된다.
스택부터 확인하는 이유 => 큐에서 확인했을때 못 넣어서 스택에 넣어버리면, 스택의 상태를 그때마다 한번 건너뛰는게 되기 때문이다.

코드

퍼포먼스

[ KB | ms ]

마무리