[BOJ] 10775 : 공항

문제 링크

10775번: 공항 (acmicpc.net)

10775번: 공항

그리디 알고리즘을 이용해서 푸는 문제

풀이 과정

보통 그리디 알고리즘 문제들을 보면 무엇을 기준으로 우선순위를 정할지 쉽게 정할 수 없는 문제들이 많지만, 이 문제는 명확했다.

i번째 비행기는 1 <= gi <= G 번째 게이트 중 하나에 들어가야한다. 어떤 비행기든지 1번 게이트에는 들어갈 수 있다. 낮은 번호의 게이트일수록 비행기가 들어갈 수 있을 확률이 높다.

즉 게이트 번호가 최대한 큰 곳부터 채워나가야 많은 비행기를 게이트에 도킹하기에 유리하다는 것이다.

도킹 가능한 가장 큰 번호를 리턴하는 get_idx 함수를 만들어 주었다.

gi 부터 한 번호씩 내려오면서 비어있는 게이트의 번호를 리턴했다. 만약 빈 공간이 없어서 0을 리턴한다면 이제 더이상 비행기가 못들어 간다는 것이므로 그때까지 들어간 비행기의 수가 답이 된다.

하지만 매번 gi 부터 하나씩 내려오면서 번호를 찾게되면 시간초과가 날 수 있다. 그래서 section 이라는 배열을 만들어서 비행기가 가득 차있는 구간을 저장해두었다. 만약 section[10] = 3 이라고 한다면 3번게이트부터 10번게이트까지는 비행기가 모두 차있다는 뜻이다. gi = 11이라고 하자. 11번게이트에 자리가 없는 것을 확인하고 10번게이트를 탐색하는데 section[10] = 3 이므로 10 ~ 3번게이트까지는 가득찬 것을 알 수 있다. 그러므로 바로 2번 게이트로가서 다시 탐색을 시작하면 된다.

#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include <cstdio>
#include <string.h>
#include <string>
#include <stack>
#include <vector>
#include <math.h>
#include <queue>
#include <climits>
#include <algorithm>
#include <iomanip>
#include <map>
#define mod 1000000007
using namespace std;
typedef long long ll;
typedef priority_queue<pair<pair<ll, int>, int>, vector<pair<pair<ll, int>, int>>, greater<pair<pair<ll, int>, int>>> Priority_queue;
const ll INF = LLONG_MAX;
const int MAX_N = 100000 + 5;
int G, P;
bool visited[MAX_N];
int section[MAX_N];
 
int get_idx(int num) {
    int temp = num;
    if (section[num] != -1) {
        num = max(section[num]-1,0);
    }
    while(1) {
        if (visited[num] == false) {
            section[temp] = num;
            break;
        }
        else if (section[num] != -1) {
            num = max(section[num]-1,0);
        }
        else num--;
    }
    return num;
}
int main(void) {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cin >> G >> P;
    memset(section, -1, sizeof(section));
    int ans = 0;
    for (int i = 1; i <= P; i++) {
        int num;
        cin >> num;
        int idx = 0;
        if (!ans) {
            idx = get_idx(num);
            if (!idx)
                ans = i - 1;
            if (idx && i == P)
                ans = i;
            visited[idx] = true;
        }
    }
    cout << ans << "\n";
    return 0;
}
 

첫 시도부터 73퍼센트까지 가면 뭔가 희망을 느끼게 돼서 더 잘 풀리는 것 같다😊