알고리즘/BOJ
[BOJ/python]3020번 개똥벌레
frog-in-well
2022. 7. 4. 22:30
문제 링크 - https://www.acmicpc.net/problem/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] 와 같이 존재하지 않는 높이 인덱스를 반복문 안에서 실행해야 하므로 비효율적이라는 것을 알게 되었다.
최종적으로 모든 석순/종유석의 입력을 받은 뒤 마지막에 큰 높이에서부터 누적하는 방식을 선택했다. 이 경우에는 정렬이 불필요한데 지워주지 않았다.