[백준][부분합] 개똥벌레

BAEKJOON Online Judge(BOJ) 문제입니다.

https://www.acmicpc.net/

Baekjoon Online Judge

 

문제

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

3020번: 개똥벌레

 

내가 작성한 코드

import sys
from collections import deque
read = sys.stdin.readline

N, H = list(map(int, read().rstrip().split(' ')))
down = []
up = []
for _ in range(N//2):
    down.append(int(read().rstrip()))
    up.append(H - int(read().rstrip()))

down = deque(sorted(down))
up = deque(sorted(up))

min_val, min_cnt = sys.maxsize, 0
for i in range(H):
    while down and down[0] < i:
        down.popleft()
    while up and up[0] < i:
        up.popleft()
    crnt = len(down) + (N //2) - len(up)
    if crnt < min_val:
        min_val, min_cnt = crnt, 1
    elif crnt == min_val:
        min_cnt += 1

print(min_val, min_cnt)

• 위/아래 중 위를 기준이라 하면
  
  • 아래의 값은 H-값으로 평가
  • 위/아래는 각 값에 대해 정렬
  • H만큼 위에서 부터 탐색
  • 현재 탐색하는 값보다 작으면 deque에서 pop
  • 위의 장애물 개수 - 아래값의 장애물 개수 (len(deque))의 최소값 찾기

 

다른 사람이 작성한 코드

n, h = map(int, input().split())
top = []
bottom = []
for i in range(n):
    if i % 2 == 0:
        bottom.append(int(input()))
    else:
        top.append(int(input()))
top.sort()
bottom.sort()
obstacles = []
for i in range(1, h+1):
    l, r = 0, len(bottom)-1
    bottomCnt = 0
    while l <= r:
        mid = (l+r)//2
        if bottom[mid] >= i:
            bottomCnt = len(bottom) - mid
            r = mid - 1
        else:
            l = mid + 1

    topCnt = 0
    l, r = 0, len(top)-1
    while l <= r:
        mid = (l+r)//2
        if h - top[mid] < i:
            topCnt = len(top) - mid
            r = mid - 1
        else:
            l = mid + 1
    obstacles.append(topCnt+bottomCnt)
res = min(obstacles)
print(res, obstacles.count(res))

• 현재 탐색중인 i값보다 작거나 같은 값의 인덱스(장애물의 개수)를 이분탐색으로 찾는 방식

 

기억해야할 것

• 처음에 문제가 2차원이라 접근이 어려웠음
• 위/아래의 시작점의 고정되어 있음을 활용