[python]백준 3020번 - 개똥벌레

BOJ

[python]백준 3020번 - 개똥벌레

yujinkimkim 2023. 8. 2. 21:52

3020번: 개똥벌레

개똥벌레 한 마리가 장애물(석순과 종유석)로 가득찬 동굴에 들어갔다. 동굴의 길이는 N미터이고, 높이는 H미터이다. (N은 짝수) 첫 번째 장애물은 항상 석순이고, 그 다음에는 종유석과 석순이

www.acmicpc.net

import sys
from bisect import bisect_left, bisect_right
input = sys.stdin.readline

n, h = map(int, input().split())

down = []
up = []
for i in range(n):
    if i % 2 == 0:
        down.append(h - int(input()))
    else:
        up.append(int(input()))
down.sort()
up.sort()

ans = []
for i in range(1, h+1):
    temp = 0
    temp += bisect_right(down, h - i)
    temp += len(up) - bisect_right(up, h - i)
    ans.append(temp)
print(min(ans), ans.count(min(ans)))

첫번째 시도 - 시간초과~

import sys
input = sys.stdin.readline

m, n = map(int, input().split())

arr = []
for i in range(m):
    arr.append(int(input()))

ans = []
for i in range(1, n+1):
    temp = 0
    for idx, item in enumerate(arr):
        if idx % 2 == 0:
            if item - i >= 0:
                temp += 1
        else:
            if item + i > n:
                temp += 1
    ans.append(temp)
print(min(ans),ans.count(min(ans)))

질문게시판 보다 bisect라고 이진탐색을 쉽게 할 수 있게 도와주는 모듈 있대서 그걸로 풀었슴니다

import sys
from bisect import bisect_left, bisect_right
input = sys.stdin.readline

n, h = map(int, input().split())

down = []
up = []
for i in range(n):
    if i % 2 == 0:
        down.append(h - int(input()))
    else:
        up.append(int(input()))
down.sort()
up.sort()

ans = []
for i in range(1, h+1):
    temp = 0
    temp += bisect_right(down, h - i)
    temp += len(up) - bisect_right(up, h - i)
    ans.append(temp)
print(min(ans), ans.count(min(ans)))

bisect_right하면 첫번째 인자로 온 배열에서 두번째 인자로 온 값보다 작거나 같은 개수 리턴해줍니다

[Python] bisect 사용법👀 / 이분탐색 / 코딩테스트 (tistory.com)