백준 10775 공항 Java

BOJ 10775번 공항 https://www.acmicpc.net/problem/10775

10775번: 공항

 

문제를 이해하는데 오래걸렸다....

⭐⭐당신은 i번째 비행기를 1번부터 gi (1 ≤ gi ≤ G) 번째 게이트중 하나에 영구적으로 도킹하려 한다.

1~Gi번째까지 모두 가능하단 얘기다

gi = 2 일 경우 1,2번 게이트 모두 가능
gi = 3 일 경우 1,2,3번 게이트 모두 가능
작은 수는 공통이므로 큰 수부터 차례대로 게이트 사용한다.

 

int 배열을 하나 만들어서 사용할 수 있는 각 게이트별로 사용할 수 있는 게이트를 등록해놓고

비행기가 들어왔을 때 사용할 수 있는 게이트에 바로 도킹하도록 해주면 된다.

해당 게이트를 사용한 경우 그 앞번호 게이트를 이용할 수 있도록 번호를 갱신한다.

모두 다 사용하면 -1이 되고, 사용가능한 번호가 -1일 경우 Close한다.

사용가능한 게이트를 등록하고, 사용하면 그 앞번호 게이트를 이용할 수 있도록 갱신.

 

매번 이렇게 사용가능한 게이트를 탐색탐색탐색 하면(연두색선) 시간초과가 발생하게 된다.

탐색탐색탐색 이란 비행기가 3번,3번,3번으로 들어갈 경우 (1) 파란색선(3번영구도킹, 2번으로 갱신) (2) 연두색선(3번 > 2번. 2번 영구도킹, 1번으로 갱신) (3) 노란색선(3번 > 2번 > 1번. 1번 영구도킹, -1로 갱신)

탐색탐색탐색 3 > 2 > 1 > -1

따라서 탐색한 결과값을 저장해주는 로직을 통해 ㅇㄷ를 박아놓을 필요가 있다

2,3을 1로 갱신하면 다음번에 3으로 들어올 경우 1로 바로가게 됨(분홍선, 빨간선)