[BOJ/백준] 3020 개똥벌레

# 3020 개똥벌레
 
N,H = map(int,input().split())
 
bottom_list = [0]*H
top_list = [0]*H
 
 
for ind in range(N):
    height = int(input())
    if ind%2:
        top_list[height] += 1
    else:
        bottom_list[height] += 1
 
for ind in range(1,H):
    bottom_list[ind] += bottom_list[ind-1]
    top_list[ind] += top_list[ind-1] 
 
bottom_list.append(bottom_list[-1])
top_list.append(top_list[-1])
min_result = float('inf')
min_cnt = 0
for k in range(H):
    bottom_cnt = bottom_list[-1] - bottom_list[k]
    top_cnt = top_list[-1] - top_list[(H-1)-k]
    if bottom_cnt +top_cnt < min_result:
        min_result = bottom_cnt+top_cnt
        min_cnt = 1
    elif bottom_cnt + top_cnt == min_result:
        min_cnt += 1
 
print(min_result,min_cnt)

prefix sum 을 이용해서 푼 방식이다.  종유석과 석순을 구분해서 prefix_sum을 해주고, 그 다음에 상황에 맞게 최저값을 구해주면 된다.

 

# 3020 개똥벌레
import sys
 
 
N,H = map(int,sys.stdin.readline().split())
 
bottom_list = [0]*(H+1)
top_list = [0]*(H+1)
 
for ind in range(N):
    height = int(input())
    if ind%2:
        top_list[height] += 1
    else:
        bottom_list[H-height+1] += 1
for ind in range(H-1,0,-1):
    top_list[ind] += top_list[ind+1]
 
 
for ind in range(2,H+1):
    bottom_list[ind] += bottom_list[ind-1]
 
min_total = N
min_cnt = 0
for ind in range(1,H+1):
    sub_sum = bottom_list[ind] + top_list[ind]
    if sub_sum < min_total:
        min_total = sub_sum
        min_cnt = 1
    elif sub_sum == min_total:
        min_cnt += 1
print(min_total,min_cnt)

이 코드는 석순의 저장 방식을 다르게 하여, 한번에 계산이 편하게 한 방식이다.