(백준 알고리즘 문제풀이) 3020번 개똥벌레

문제

 

문제 링크

 

문제 접근

• N(짝수): 동굴의 길이
• H: 동굴의 높이
• 종유석과 석순이 번갈아가면서 등장한다
• 종유석: 아래에서부터 등장
• 석순: 위에서부터 등장
• 짝수번째 인덱스: 종유석, 홀수번째 인덱스: 석순으로 지정후 리트스 추가

코드

import sys

N, H = map(int, sys.stdin.readline().split())

up = [0] * (H+1)
down = [0] * (H+1)
count = [0] * (H+1)

for i in range(N):
    temp = int(sys.stdin.readline())
    if i % 2 == 0:
        down[temp] += 1
    else:
        up[H-temp+1] += 1

for j in range(H-1, 0, -1):
    down[j] += down[j+1]

for k in range(2, H+1):
    up[k] += up[k-1]

for s in range(1, H+1):
    count[s] = down[s] + up[s]

min_count = min(count[1:])
print(min_count, count[1:].count(min_count))

느낀점

for문을 너무 많이 쓴거 같다. 다른 사람들 풀이를 보면 이분탐색을 이용하던데 한번 코드리뷰를 해보아야겠다.