백준16288 Passport Control

작성일 | In

문제 링크

  • http://icpc.me/16288

문제 출처

  • 2018 ACM-ICPC 서울 인터넷 예선 G번

사용 알고리즘

  • Stack

시간복잡도

  • O(nk)

풀이

1부터 10까지의 수를 3개의 큐에 적절하게 배치해 4 1 3 2 5 6 8 9 7 10 순서대로 뺄 수 있을지를 판단해봅시다.
직접 3개의 큐를 만들어서 시뮬레이션을 돌리는 방법을 고려해볼 수 있습니다. 그러나 구현이 귀찮으므로 다른 방법을 찾아봅시다.

큐에 적절히 넣고 빼서 특정 순서를 만드는 것이 가능한지 판단하는 것 대신, 역으로 이미 빠져나온 결과에서 시작해 큐로 돌려보내는 작업을 통해서도 판단할 수 있습니다.
monotone stack이라고 불리는 기법이 있습니다. 해당 기법에 대한 설명은 (이 글)에 있습니다.
monotone stack은 스택을 증가 혹은 감소시키기 위해 해당 조건을 위배하는 원소가 있다면 그 원소를 스택에서 제거를 했습니다. 비슷한 아이디어를 사용해 이 문제는 조건을 위배하는 원소가 들어오면 없애는 것이 아닌 다음 큐에 넣어주면 됩니다.

전체 코드

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
#include <bits/stdc++.h>
using namespace std;

stack<int> s[110];

int main(){
	int n, k; cin >> n >> k;
	vector<int> v(n);
	for(int i=0; i<n; i++) cin >> v[i];

	reverse(v.begin(), v.end());

	for(int i=0; i<100; i++) s[i].push(1010);
	for(int i=0; i<n; i++){
		int idx = 0;
		int j;
		for(j=0; j<k; j++){
			if(s[j].top() > v[i]) break;
		}
		if(j == k){
			cout << "NO"; return 0;
		}

		s[j].push(v[i]);
	}
	cout << "YES";
}