[백준] 10775번 공항 (C++)

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

 

이 문제는 G개의 게이트가 존재하며 P개의 비행기가 공항으로 들어올때 도킹을 해야하는데

이때 비행기를 1부터 비행기의 번호 중 하나에 영구적으로 도킹을 할 수 있다.

 

만약 중간에 도킹할 자리가 없으면 공항이 폐쇄되고 그전까지 도킹했던 개수를 출력하는 문제이다.

 

그렇다면 비행기가 들어오는 번호에서부터 bool 방문배열을 사용하여 하나씩 줄여가며 넣을 수 있으면 넣고 못넣는 경우

중지시켜 값을 출력하면 되지 않을까 생각하지만

 

Q, P의 값이 최대 10만이다 -> 최악의 시간복잡도는 O(10^10)이다.

 

그렇다면 기록을 하면 되지 않을까 생각이든다.

visited[i] = j 가 의미하는 것은 i의 비행기가 들어오면 j에 도킹을 해라라는 의미이다.

같은 로직이지만 memozation을 하여 기록해두면 시간이 훨씬 단축될 것이다.

 

정답 코드

#include <bits/stdc++.h>
using namespace std;
typedef pair<int, int> pii;
typedef long long ll;
#define endl "\n"
#define MAX 1e9

struct coordinate {
    int x;
    string s;
    vector<int> v;
};

int dx[] = {-1, 0, 1, 0, 1, -1, -1, 1};
int dy[] = {0, 1, 0, -1, -1, 1, -1, 1};
int G, P;
int nextPos[100001];
bool visited[100001];

void Init() {
    for(int i = 1; i <= G; i++) {
        nextPos[i] = i;
    }
}

void input() {
    cin >> G >> P;

    Init();

    int cnt = 0;

    for(int i = 0; i < P; i++) {
        int a;
        cin >> a;

        int loc = nextPos[a];

        while(loc >= 1 && visited[loc]) loc--;

        if(loc == 0) break;

        visited[loc] = true;
        cnt++;
        nextPos[a] = loc-1;
    }

    cout << cnt;
}

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0), cout.tie(0);

    input();
}