[백준 16288번] [그리디] Passport Control

처음에 진짜 개똥짓해서 어마어마하게 디버깅하고, 어마어마하게 고민한 문제이다.

 

처음 세웠던 논리는 다음과 같다.

1. 맨 뒤부터 시작하여 해당하는 숫자보다 더 왼쪽에 있는 숫자가 만약 더 크게 되면 그 숫자는 절대로 같은 큐상에 위치할 수 없다.

2. 이를 활용하여 각 index별로 위치할 수 있는 큐의 갯수를 찾고 만약 0이라면 NO를 출력하면 된다.

혹은

1. 맨 앞부터 시작하여 해당하는 숫자보다 더 오른쪽에 있는 숫자가 만약 더 작데 되면 그 숫자는 절대로 같은 큐상에 위치할 수 없다.

2. 이를 활용하여 각 index별로 위치할 수 있는 큐의 갯수를 찾고 만약 0이라면 NO를 출력하면 된다.

특히 이 방법을 시도하면서 착각하였던 부분이
후자의 접근 방법의 경우 만약 오른쪽에 있는 숫자가 더 큰 것이 중간에 들어갈 경우에 대해서는 무시하고 진행해도 된다고 판단하였다. 그런데 생각해보면 종속적으로 움직이는 것이므로 이렇게 판단할 수 없다.
(진짜.. 이것 때문에 엄청나게 시간을 썼다...)

너무 안풀려서 인터넷에서 살짝 힌트를 얻었다.

사실 기본적으로 처음 세웠던 논리와 유사한데, 큐가 FIFO구조이므로 각 큐에서는 무조건 증가수열일수밖에 없다.

즉, 최대증가수열의 갯수가 Passport의 갯수보다 작으면 해당하는 경우를 생성할 수 있는 것이다.

 

위의 내용을 코드로 구현한 결과는 다음과 같다.

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;
int passenger_num, passport_num;
vector<int> data_store;
int visited[101];

int main(void){
    cin >> passenger_num >> passport_num;
    fill_n(visited, 101, 0); // Initialize

    for(int i = 0; i < passenger_num; i++){
        int temp;
        cin >> temp;
        data_store.push_back(temp);
    }

    int count = 0;

    for(int i = 0; i < passenger_num; i++){
        if(visited[data_store[i]] == 1) continue; // Already visited
        else{
            visited[data_store[i]] == 1;
            int check_num = data_store[i];
            for(int j = i + 1; j < passenger_num; j++){
                if(check_num < data_store[j] && visited[data_store[j]] != 1){
                    check_num = data_store[j];
                    visited[data_store[j]] = 1; // Visited processing
                }
            }
            count += 1;
        }
    }

    if(count <= passport_num){
        cout << "YES\n";
    }
    else{
        cout << "NO\n";
    }
    return 0;
}

참.. 더럽게 힘들었다..