📚 2891 - 카약과 강풍

카약과 강풍

이해

시간 제한이 1초인 그리디 알고리즘이다.

✔ 경우의 수

• 카약이 손상된 팀의 번호가 주어진다.
• 카약을 하나 더 가져온 팀의 번호가 주어진다.

여기서, 카약이 손상된 팀 중에서 카약을 하나 더 가져온 팀의 번호가 주어질 수 있다.

이분 탐색을 사용하여 구현하였다.

소스

import sys  
  
read = sys.stdin.readline  
  
n, s, r = map(int, read().split())  
  
arr = [0] * (n)  
  
arr = [-200] + arr  
  
damage = list(map(int, read().split()))  
heal = list(map(int, read().split()))  
  
for in_d in damage:  
    arr[in_d] += -1  
for in_h in heal:  
    arr[in_h] += 1  
  
  
def binary_divide(start, end):  
    if start > end:  
        return  
  
    mid = (start + end) // 2  
  
    if arr[mid] == 1:  
		# 왼쪽 i - 1, - 2 번째가 손상된 경우
        if mid - 2 > 0 and arr[mid - 1] == -1 and arr[mid - 2] == -1:  
            arr[mid - 1], arr[mid] = 0, 0  
		# 오른쪽 i + 1, + 2 번째가 손상된 경우
        elif mid + 2 <= n and arr[mid + 1] == -1 and arr[mid + 2] == -1:  
            arr[mid + 1], arr[mid] = 0, 0  
		# 왼쪽 i - 1번째가 손상된 경우
        elif mid - 1 > 0 and arr[mid - 1] == -1:  
            arr[mid - 1], arr[mid] = 0, 0  
		# 오른쪽 i + 1번째가 손상된 경우
        elif mid + 1 <= n and arr[mid + 1] == -1:  
            arr[mid], arr[mid + 1] = 0, 0  
  
    binary_divide(start, mid - 1)  
    binary_divide(mid + 1, end)  
  
  
binary_divide(1, n)  
  
print(arr.count(-1))