[Python][백준] 3020_개똥벌레

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

3020번: 개똥벌레

문제

개똥벌레 한 마리가 장애물(석순과 종유석)로 가득찬 동굴에 들어갔다. 동굴의 길이는 N미터이고, 높이는 H미터이다. (N은 짝수) 첫 번째 장애물은 항상 석순이고, 그 다음에는 종유석과 석순이 번갈아가면서 등장한다.

아래 그림은 길이가 14미터이고 높이가 5미터인 동굴이다. (예제 그림)

이 개똥벌레는 장애물을 피하지 않는다. 자신이 지나갈 구간을 정한 다음 일직선으로 지나가면서 만나는 모든 장애물을 파괴한다.

위의 그림에서 4번째 구간으로 개똥벌레가 날아간다면 파괴해야하는 장애물의 수는 총 여덟개이다. (4번째 구간은 길이가 3인 석순과 길이가 4인 석순의 중간지점을 말한다)

하지만, 첫 번째 구간이나 다섯 번째 구간으로 날아간다면 개똥벌레는 장애물 일곱개만 파괴하면 된다.

동굴의 크기와 높이, 모든 장애물의 크기가 주어진다. 이때, 개똥벌레가 파괴해야하는 장애물의 최솟값과 그러한 구간이 총 몇 개 있는지 구하는 프로그램을 작성하시오.

 

입력

첫째 줄에 N과 H가 주어진다. N은 항상 짝수이다. (2 ≤ N ≤ 200,000, 2 ≤ H ≤ 500,000)

다음 N개 줄에는 장애물의 크기가 순서대로 주어진다. 장애물의 크기는 H보다 작은 양수이다.

 

출력

첫째 줄에 개똥벌레가 파괴해야 하는 장애물의 최솟값과 그러한 구간의 수를 공백으로 구분하여 출력한다.

---

누적합(Prefix Sum) 연습을 위해서 풀었던 문제라 풀이 방법을 고민할 필요가 없었음에도, 쉽지 않았던 문제였다.

 

풀이순서는 다음과 같다.

(1) h높이의 석순과 종유석이 몇개 있는지 각각 배열에 저장

-> X[h] = h높이 석순 갯수, Y[h] = h높이 종유석 갯수

 

(2) 석순과 종유석의 누적합 각각 구하기

-> 경로 별로 부딪히는 장애물의 갯수를 하나씩 다 체크해주면 O(H^2)가 된다. 문제에서 최대 H가 500,000이기 때문에 당연히 시간초과가 발생한다. 이 때, 길이가 1이라면 1번 경로에서만 장애물, 길이가 H라면 H보다 작은 모든 경로에서 장애물이 되는 규칙을 이용해 아래와 같이 누적합을 구하면 시간을 줄일 수 있다. 누적합을 구하는 start는 석순과 종유석이 각각 최대 H를 가질 때이다.

 

<석순>

<종유석>

 

(3) 경로별 석순과 종유석에 부딪히는 갯수 합하기

--> P[n] = Px[n] + Py[n]

 

(4) Counter를 사용하여 최소로 부딪히는 갯수와 그 경우의 수 가져오기

--> 3번까지의 과정을 통해 P[n]에는 n번 경로로 이동할 때 부딪히는 석순과 종유석의 총 갯수를 담는다.

이 값이 각각 몇개씩 배열에 존재하는지 쉽게 구할 수 있는 collections.Couter를 사용한다.

Key를 오름차순을 정렬하여 가장 작은 Key 값과 그 Value값을 출력한다.

 

import sys
from collections import Counter

N, H = map(int, sys.stdin.readline().strip().split()) # N: 장애물 갯수(동굴길이), H: 동굴 높이
X, Y = [ 0 for _ in range(H+1)], [ 0 for _ in range(H+1)] # X: 석순, Y: 종유석

for r in range(N): # num 길이의 석순/종유석이 몇개 있는지 X,Y배열에 cnt
    num = int(sys.stdin.readline())
    if r % 2 == 0: # 짝수 ==> 석순
        X[num] += 1
    else: # 홀수 ==> 종유석
        Y[num] += 1

Px, Py = [ 0 for _ in range(H+1)], [ 0 for _ in range(H+1)] # 석순, 종유석의 prefix sum
Px[H], Py[1] = X[H], Y[H]

# prefix sum
for r in range(1, H):
    Px[H-r] = Px[H-r+1] + X[H-r] # R-1경로 석순 갯수 = R경로 석순 갯수 + (R-1)높이 석순 갯수
    Py[r+1] = Py[r] + Y[H-r] # R+1경로 종유석 갯수 = R경로 종유석 갯수 + (H-R)높이 종유석 갯수

# 석순 + 종유석
P = [ 0 for _ in range(H)]
for r in range(H):
    P[r] = Px[r+1] + Py[r+1]

#Counter
c = Counter(P) # {Key: x경로로 갔을 때의 장애물 갯수, Value: 그런 경로의 갯수}
minXY = list(sorted(c.keys()))[0] # Key 오름차순으로 정렬
print(minXY, c[minXY]) # 최소 장애물 갯수, 경로 갯수