[파이썬] 백준 3020 : 개똥벌레

[파이썬] 백준 3020 : 개똥벌레

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

3020번: 개똥벌레

난이도 : 골드 5

누적합

---

종유석(천장에 박힌 것) 석순(바닥에 박힌 것)이 특정 높이에 있을 때의 누적합을 구해야 한다.

 

예제 입력 1을 예시로 석순 부분만 그림으로 나타내면 다음과 같다.

개똥벌레가 파괴해야하는 장애물이 가장 많은 구간은 높이가 1일 때의 구간이다. 총 3개의 석순을 부숴야 한다.

높이가 2, 3인경우 2개의 석순을, 높이가 4, 5인 경우 1개의 석순을 파괴해야 한다.

석순에 어떤 값이 들어오든, 높이가 제일 낮은 석순이 있는 구간에서 파괴해야할 석순의 수가 가장 많다는 규칙을 발견할 수 있다.

이 경우, 누적합 알고리즘을 활용해서 문제를 풀어낼 수 있다.

누적합을 할당하는 아이디어는 다음과 같다.

주어진 높이 만큼의 리스트를 설정하고 최종적으로 각 인덱스(구간)에 개똥벌레가 파괴해야하는 장애물의 수를 할당한다.

 

bottom이라는 리스트는 석순들에 대한 정보를 할당받는다.

 

bottom = [0] * (H+1)

높이가 7이므로 인덱스 할당의 편의를 위해 8개를 선언했다.

석순들을 입력받으면 다음과 같이 할당된다.(1, 3, 5)

bottom[int(input())] += 1

이렇게 되면 높이 1, 3, 5의 구간에서 파괴해야 할 장애물의 수가 모두 1개씩으로 매겨진다.

여기서 가장 높은 높이에서 반대로 순회하면서 가장 적은 높이로 누적합을 해주는 방식을 적용하면 된다.

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

반복문을 거꾸로 돌리면서 인덱스 오른쪽에 있는 값을 현재 인덱스 값에 더해주는 방식이다.

그럼 다음과 같이 값이 할당 된다.

 

그럼 처음에 의도했던 그림대로 리스트에 값을 할당할 수 있다.

 

이번엔 종유석의 경우를 살펴보자.

종유석은 예제 입력1의 경우 5, 3, 1의 크기로 주어진다.

이번에는 높이(구간)가 천장에 가까울수록 파괴해야 할 장애물의 개수가 늘어난다는 것을 확인할 수 있다.

따라서 누적합은 다음과 같이 할당해야 한다.

리스트에 값을 할당하기 전에, 석순과 종유석의 그림을 먼저 합쳐보도록 하자.

아까 석순에 값을 할당할 때 각 구간(인덱스)은 땅바닥을 기준으로 했기 때문에 종유석 리스트에 값을 넣을 때도 똑같은 기준을 적용해야 한다.

 

결국 3, 5, 7번 인덱스에 종유석 값을 할당해주어야 하는 것이다.

높이가 H일때, 종유석으로 입력한 값이 num이라면

H-num+1로 해당 구간의 값을 구할 수 있다.

 

종유석 리스트를 top이라고 했을 때의 코드는 다음과 같다.

top = [0] * (H+1)

높이가 7이므로 인덱스 할당의 편의를 위해 8개를 선언했다.

top[H-int(input())+1] += 1

종유석은 석순과 반대로, 높이가 높아질 수록 파괴해야할 장애물의 개수가 증가하도록 구현해야 한다.

for i in range(1, H+1):
  top[i] += top[i-1]

 

bottom과 top에서 각 높이(구간)에서의 파괴해야 할 장애물의 개수가 모두 등록이 되었으므로 이제 두 값을 합한 값을 새로운 리스트에 할당하고, 그 리스트 내의 최소값과 빈도를 체크해주면 되겠다.

 

전체 코드는 다음과 같다.

 

import sys
input = sys.stdin.readline
N, H = map(int, input().split())
top = [0] * (H+1)
bottom = [0] * (H+1)
answer = [0] * (H+1)

for i in range(1, N+1):
  if i%2 == 0:
    top[H-int(input())+1] += 1
  else:
    bottom[int(input())] += 1

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

for i in range(1, H+1):
  top[i] += top[i-1]

for i in range(1, H+1):
  answer[i] = top[i] + bottom[i]

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

answer[0]에는 항상 0이 있기 때문에 그냥 min(answer)를 구하면 0이 튀어나온다.

따라서 answer = answer[1:]과 같은 방식으로 0번 인덱스 값을 제외하여 재할당 한 것이다.