-
[BOJ/python]3020번 개똥벌레알고리즘/BOJ 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] 와 같이 존재하지 않는 높이 인덱스를 반복문 안에서 실행해야 하므로 비효율적이라는 것을 알게 되었다.
최종적으로 모든 석순/종유석의 입력을 받은 뒤 마지막에 큰 높이에서부터 누적하는 방식을 선택했다. 이 경우에는 정렬이 불필요한데 지워주지 않았다.
'알고리즘 > BOJ' 카테고리의 다른 글
[BOJ/python]2473번 세 용액 (0) 2022.07.04 [BOJ/python]21757번 나누기 (0) 2022.07.04 [BOJ/python]1092번 배 (0) 2022.07.04 [BOJ/python]10775번 공항 (0) 2022.07.04 [BOJ/python]1765번 닭싸움 팀 정하기 (0) 2022.07.03