[ICPC][BOJ] 16288 - Passport Control

문제 : https://www.acmicpc.net/problem/16288

---

[알고리즘풀이]

A[] : 입국장을 빠져나가는 순서를 담은 배열.

k : 여권 심사 창구의 수.

C : A배열에서 순증가부분수열의 수.

라고 한다면 k 가 C보다 크거나 같으면 항상 원하는 순서대로 입국장을 빠져나갈 수 있다.

 

ex)

A[] : 4 1 3 2 5 6 8 9 7 10 라고 하자.

A배열의 순증가부분수열은 4 - 5 - 6 - 8 - 9 - 10 / 1 - 3 - 7 / 2 로 총 3개이다.

즉, 창구가 3개 이상이면 각 창구마다 위의 수열대로 배치를 할 수 있다.

#include<iostream>

using namespace std;

bool check[101];
int A[100];

int main(void) {
	ios::sync_with_stdio(false);
	cin.tie(0); cout.tie(0);
	int n, k;
	cin >> n >> k;
	for (int i = 0; i < n; i++)
		cin >> A[i];
	int c = 0;
	for (int i = 0; i < n; i++) {
		if (check[A[i]] == false) {
			c++;
			int last = A[i];
			for (int j = i; j < n; j++) {
				if (last <= A[j] && check[A[j]] == false) {
					last = A[j];
					check[A[j]] = true;
				}
			}
		}
	}
	if (c <= k)
		cout << "YES\n";
	else
		cout << "NO\n";
	return 0;
}

---