[백준/Python] 3020번 - 개똥벌레

문제

백준 3020번 - 개똥벌레

누적합 해결 과정

1. 입력 받기

• 석순과 종유석을 각각 입력 받는다.
• 짝수는 석순이고, 홀수는 종유석
• 인덱스를 길이로, 인덱스 길이를 가진 장애물의 개수를 세어준다.
  down = [0, 1, 1, 4, 1, 0]
  ex) 석순 중에서 길이가 1인 것은 1개, 2인 것은 1개..
  up = [0, 0, 2, 3, 2, 0]
  ex) 종유석 중에서 길이가 2인 것은 2개, 3인 것은 3개..

2. 누적합 구하기

• 높이 h부터 1까지 개수의 합을 구한다.
• 높이 h부터 높이 1까지 누적 합을 계산하면 높이 i의 배열 값은 높이 i 이상의 모든 석순/종유석의 개수가 된다.
  down = [0, 7, 6, 5, 1, 0]
  ex) 높이가 4이상인 석순의 개수는 1개, 높이가 3이상인 석순의 개수는 5개..
  up = [0, 7, 7, 5, 2, 0]
  ex) 높이가 4이상인 석순의 개수는 2개, 높이가 3이상인 종유석의 개수는 5개..

3. 파괴해야하는 장애물의 최소값과 최소값이 나타나는 구간의 수 구하기

• 구간은 아래에서부터 위로 증가하기 때문에 종유석은 h-구간+1로 계산
• 최소값보다 작다면 최소값을 갱신하고, 구간 개수를 1로 초기화
  최소값이랑 같다면, 구간 개수에 1을 더해준다.

이분탐색 해결 과정

1. 입력 받기

• 석순과 종유석을 각각 입력 받는다.
• 짝수는 석순이고, 홀수는 종유석
• 석순과 종유석의 길이를 배열에 추가한다. 그리고 정렬
  down = [1, 2, 3, 3, 3, 3, 4]
up = [2, 2, 3, 3, 3, 4, 4]

2. 이분탐색 함수 만들기

• start와 end 값은 항상 같으므로
  start = 0
  end = 배열의 길이 + 1
• 구간이 target일 때 개똥벌레가 파괴하는 갯수를 반환
  (정확히는 target이 리스트에 삽입될 위치를 반환)

3. 파괴해야하는 장애물의 최소값과 최소값이 나타나는 구간의 수 구하기

• 석순
  구간이 i일 때, 리스트의 인덱스는 0부터 시작하니까, i-1
  ex) 구간이 1일 때는 7개 파괴, 2일 때는 6개 파괴...
• 종유석
  구간이 i일 때, 구간은 아래에서부터 위로 증가하기 때문에 종유석은 h-구간
  ex) 구간이 1일 때는 0개 파괴, 2일 때는 2개 파괴..
• total = 석순에서 파괴되는 장애물 + 종유석에서 파괴되는 장애물
• 최소값보다 작다면 최소값을 갱신하고, 구간 개수를 1로 초기화
  최소값이랑 같다면, 구간 개수에 1을 더해준다.

시행착오

• 곧이 곧대로 일일이 사이즈 시간초과 ;;

import sys
# 동굴의 길이와 높이
n, h = map(int, sys.stdin.readline().split())

arr = []
ans = [0] * (h+1)

for _ in range(n):
  arr.append(int(sys.stdin.readline()))

for i in range(1,h+1):
  for j in range(len(arr)):
    if j == 0 or j % 2 == 0:
      if arr[j] >= i:
        ans[i] += 1
    else:
      if (h-arr[j]) < i:
        ans[i] += 1


print(min(ans[1:]), ans.count(min(ans[1:])))

누적합 풀이

import sys
# 동굴의 길이와 높이
n, h = map(int, sys.stdin.readline().split())

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

for i in range(n):
  # 석순
  if i % 2 == 0:
    down[int(sys.stdin.readline())] += 1
  # 종유석
  else:
    up[int(sys.stdin.readline())] += 1

# 누적합 구하기
for i in range(h-1,0,-1):
  down[i] += down[i+1]
  up[i] += up[i+1]

# 파괴해야하는 장애물의 최소값
min_cnt = n
# 최소값이 나타나는 구간의 수
range_cnt = 0

for i in range(1,h+1):
  if min_cnt > (down[i]+up[h-i+1]):
    min_cnt = down[i]+up[h-i+1]
    range_cnt = 1
  elif min_cnt == down[i]+up[h-i+1]:
    range_cnt += 1

print(min_cnt,range_cnt)

이분탐색 풀이

import sys
# 동굴의 길이와 높이
n, h = map(int, sys.stdin.readline().split())

# 석순, 종유석
down, up = [], []
for i in range(n):
  # 석순
  if i % 2 == 0:
    down.append(int(sys.stdin.readline()))
  # 종유석
  else:
    up.append(int(sys.stdin.readline()))

down.sort()
up.sort()

min_cnt = int(1e9)
cnt = 0
# 이분탐색
def binary_search(target, arr):
  start = 0
  end = len(arr)-1
  while start <= end:
    mid = (start + end) // 2
    if arr[mid] <= target:
      start = mid + 1
    else:
      end = mid - 1
  return len(arr) - (end+1)

for i in range(1, h+1):
  u, d = binary_search((h-i),up), binary_search(i-1,down) 
  total = u+d
  if total < min_cnt:
    min_cnt = total
    cnt = 1
  elif total == min_cnt:
    cnt += 1

print(min_cnt,cnt)