[그리디] BOJ 16288 Passport Control

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

16288번: Passport Control

문제 해결 알고리즘

 

문제가 약간 어렵게 느껴지나 생각을 조금만 해보면 풀 수 있는 쉬운 문제였다.

 

입력에서 주어진 수열의 연속하는 증가하는 수열의 개수가 여권 심사 창구(k)보다 많다면 불가능한 순서이고 적거나 같다면 가능한 순서이다.

 

 

예를 들어, 예제에 나온 입력을 보자

 

10 3
4 1 3 2 5 6 8 9 7 10

 

여기서 연속하는 증가하는 수열은 

 

4 5 6 8 9

1 3

2 7 10 이다.

 

이런 방식으로 창구에 들어갔다가 랜덤으로 나온 것이기 때문에 연속하는 증가하는 수열의 개수를 구해주는 것이다.

 

소스 코드

 

#include <bits/stdc++.h>
using namespace std;

int main(){
    int N, k; cin >> N >> k;
    int cnt = 0;

    vector<int> v(N); 

    for(int i=0;i<N;i++){
        cin >> v[i];
    }

    for(int i=0;i<N;i++){ // 연속되는 증가하는 수열의 개수를 찾기
        if(v[i] == 0) continue;

        int idx = v[i];
        v[i] = 0;
        for(int j=i+1;j<N;j++){
        	if(v[j] == 0) continue;
            if(v[j] > idx){
                idx = v[j];
                v[j] = 0;
            }
        }

        cnt++;
    }

    if(cnt <= k) cout << "YES";
    else cout << "NO";

}