탑승구

탐승구

Question

공항에 G개의 탑승구가 있다. 이때 P 개의 비행기가 착륙을 해서 탑승구 하나에 도킹을 하게 된다.단, 비행기 마다 도킹할 수 있는 탑승구의 조건이 있는데, 비행기는 각각 g_i 값을 가지는데, 해당 비행기는 1~g_i 까지의 탑승구 중에 하나를 선택해서 도킹할 수 있다. 또한, 한 번 도킹하면 같은 탑승구에 다른 비행기는 도킹할 수 없다.

이때, 최대로 도킹할 수 있는 비행기의 수는?

문제의 조건에서 보듯이 한 비행기는 1~g_i 의 탑승구를 선택할 수 있고, 한번 도킹을 완료한 탑승구는 더 이상 추가적인 도킹을 할 수 없다. 이것을 보아 도킹 해서 자리가 없는 탑승구는 다른 탑승구로 연결을 해야한다. 비행기는 자신에 설정되어 있는 탑승구에 자리가 없으면 바로 전 탑승구부터 돌아보면서 빈 탑승구에 도킹할 수 있다. 따라서, 도킹이 완료된 탑승구는 바로 앞 탑승구로 연결시키면 된다.

즉, 해당 문제는 탑승구를 disjoint set으로 관리하면 쉽게 문제를 풀 수 있다.

Solution

def find_parent(parent,x):
  if parent[x] != x:
    parent[x]=find_parent(parent,parent[x])
  return parent[x]

def union(parent,x,y):
  pre_x=find_parent(parent,x)
  pre_y=find_parent(parent,y)

  if pre_x < pre_y:
    parent[pre_y]=pre_x
  else:
    parent[pre_x]=pre_y

if __name__ == "__main__":

  gate_num=int(input())
  plane_num=int(input())
  result=0

  Gates=[i for i in range(gate_num+1)]
  for _ in range(plane_num):
    parking_gate=int(input())
    if Gates[parking_gate]==0:
      continue
    else:
      union(Gates,parking_gate,parking_gate-1)
      result+=1

print(result)