백준 3020. 개똥벌레

bbumjun·2020년 7월 1일
0

3020. 개똥벌레

문제링크

| 난이도 | 정답률(_%) |
| :----: | :---------: |
| Gold V | 40.000% |

| 메모리 (KB) | 시간 (ms) |
| :---------: | :-------: |
| 154292 | 536 |

설계

  1. 석순과 종유석을 두개의 list로 분리해서 입력을 받는다.
  2. 이분탐색을 위해 각각 오름차순으로 정렬한다.
  3. 동굴의 높이만큼 for 문을 돌면서 모든 층에서의 개똥벌레가 부숴야할 장애물을 센다.
  4. 각 층에서 장애물의 갯수를 셀 때, 층에 걸리는 장애물의 크기중 가장 작은 것를 이분탐색을 통해 찾아 그 층에서의 장애물의 갯수를 셀 수 있다.
  5. 각 층에서의 장애물의 갯수 중 최솟값과 최솟값의 갯수를 출력한다.

시간복잡도

O(H * logN)

코드

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))
profile
Wanna be a Front-end developer

0개의 댓글