[BOJ/python]3020번 개똥벌레

문제 링크 - https://www.acmicpc.net/problem/3020

3020번: 개똥벌레

석순과 종유석의 길이가 주어지면 석순과 종유석이 가장 적게 등장하는 구간을 찾는다.

1. 풀이

누적합 문제다. 석순과 종유석이 번갈아가며 주어진다는 점에서 힌트를 얻어서 석순과 종유석을 분리했다.

• 가장 처음 등장하는 원소는 석순이므로 down 배열에 0번째 원소부터 1개씩 건너 뛰며 저장한다. up 배열에는 1번째 원소부터 1개씩 건너 뛰며 저장한다.
• prefix배열에서 각 인덱스의 크기는 높이를 의미한다. 길이가 5인 석순이 있다면 prefix[5]의 값에 1을 더해준다. 각각의 석순에 대하여 해당 계산을 반복한다.
• 가장 큰 높이에서부터 누적합을 통해 각 높이 구간의 석순의 개수를 갱신해준다. 높이가 5인 석순이 3개라면 높이 4인 구간(prefix[4])에도 3개를 추가해준다. (갱신된 prefix[4]를 prefix[3]에 더해준다.)
• 종유석의 경우에는 천장을 바닥으로 생각하고 계산한 뒤 천장에서 부터 인덱스를 늘려가며 석순/종유석 누적합 배열을 하나로 합쳤다.
• 완성된 누적합 배열에서 최솟값과 최솟값의 개수를 출력한다.

2. 코드

#개똥벌레 (누적합)
import sys
input = sys.stdin.readline

N,H = map(int, input().split())
A= [ int(input()) for _ in range(N)] # 전체 저장
prefix=[0 for _ in range(H+1)] #석순 저장
prefix2=[0 for _ in range(H+1)] # 종유석 저장
down = A[::2]   # 석순
up = A[1::2]    # 종유석

down.sort(reverse=True)
up.sort(reverse=True)

idx=down[0] #길이가 큰 석순부터
for i in range(len(down)):
    if down[i]==idx:
        prefix[idx]+=1
    
    else:
        idx=down[i]
        prefix[idx]+=1

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

idx=up[0] #길이가 큰 종유석부터
for i in range(len(up)):
    if up[i]==idx:
        prefix2[idx]+=1
        
    else:   #길이가 다른 종유석 등장하면 길이(인덱스) 갱신
        idx=up[i]
        prefix2[idx]+=1
        
#누적합 구하기
for i in range(H-1, 0,-1):
    prefix2[i]+=prefix2[i+1]
    

for i in range(1, H+1):
    prefix[i] += prefix2[H+1-i]
sol=prefix[1:]
tmp = min(sol)
print(tmp,sol.count(tmp))

3. 개선할 점

처음에는 반복문을 돌리며 석순/종유석의 높이에 해당하는 prefix 배열에 추가하고 석숙/종유석의 높이가 바뀔 때마다 누적합을 계산하기 위해 주어진 배열을 정렬한 뒤 구현했다.

그러나 만약 주어진 석순의 높이가 5,2,1 이라면 prefix[5]=1, prefix[4]+=prefix[5], prefix[3]+=prefix[2] 와 같이 존재하지 않는 높이 인덱스를 반복문 안에서 실행해야 하므로 비효율적이라는 것을 알게 되었다.

최종적으로 모든 석순/종유석의 입력을 받은 뒤 마지막에 큰 높이에서부터 누적하는 방식을 선택했다. 이 경우에는 정렬이 불필요한데 지워주지 않았다.