파이선) 개똥벌레 - BOJ

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

3020번: 개똥벌레

 

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

arr = []
top = []
bottom = []

for i in range(n):
    if i % 2 == 0:
        bottom.append(int(input()))
    else:
        top.append(int(input()))


top.sort()
bottom.sort()

start = 1
end = h

cnt = 0
min_v = int('inf')
while start <= end:
    mid = (start + end) // 2
    print('mid = ', mid)
    wall = 0

    for i in top:
        if h - i < mid:
            print('top', i)
            wall += 1

    for i in bottom:
        if i >= mid:
            print('bot', i)
            wall += 1

    if min_v == wall:
        cnt += 1
    elif min_v > wall:
        min_v = wall
        cnt = 1

    else:

처음 제출한 코드이다.

이분탐색으로 풀려 시도했지만 동굴의 장애물 높이가 각각 아래와 위에 붙어있어 어느 조건일때 start를 높이고 어느 조건일때 end를 높일지 감이오질 않았다.

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

top = [0] * (h + 1)
bottom = [0] * (h + 1)

for i in range(h):
    idx = int(input())

    if i % 2 == 0:
        bottom[idx] += 1
    else:
        top[idx] += 1


for i in range(h-1, -1, 0):
    bottom[i] += bottom[i+1]
    top[i] += top[i+1]


min_v = int('inf')
cnt = 0
for i in range(1, h+1):
    walls = bottom[i] + top[h-i + 1]

    if walls == min_v:
        cnt += 1
    elif walls < min_v:
        cnt = 1
        min_v = walls


print(min_v, cnt)

누적합으로 푼 코드이다.

이 코드는 시간초과가 발생했다.

그래서 이렇게 푸는게 아닌가 싶어서 다른 사람의 코드를 참조했다.

 

import sys

# 장애물의 개수와 전체 높이
n, h = map(int, sys.stdin.readline().split())

# 석순 정보 저장
down = [0] * (h+1)
# 종유석 정보 저장
up = [0] * (h+1)

# 장애물의 크기 입력
for i in range(n):

    height = int(sys.stdin.readline())

    if (i % 2 == 0):
        # 석순의 높이에 따라 1 증가
        down[height] += 1
    else:
        # 종유석의 높이에 따라 1 증가
        up[height] += 1

# 인덱스를 역순으로 누적합을 계산
for i in range(h-1, 0, -1):
    down[i] += down[i+1]
    up[i] += up[i+1]

# 최소로 잘리는 장애물의 개수
min_count = n

# 동일한 개수로 잘리는 높이의 수
same_height = 0

# 전체 높이 i 기준, 높이에 따라 잘리는 석순과 종유석의 개수 파악
for i in range(1, h+1):

    # 현재까지 최소로 잘린 개수보다 현재 높이에서 더 적은 수로 잘리는 경우
    if (min_count > down[i] + up[h - i + 1]):
        min_count = down[i] + up[h - i + 1]
        same_height = 1

    # 현재 높이에서 잘린 개수가 현재까지 최소로 잘린 개수와 동일하다면
    elif (min_count == down[i] + up[h - i + 1]):
        same_height += 1

print(min_count, same_height)

별 달라진건 없지만 input에서 아슬아슬하게 타임아웃이 나온것 같다..