[백준 3020] 개똥벌레 (Python)

www.acmicpc.net/problem/3020

3020번: 개똥벌레

 

문제풀이

N, H : 입력값(가로, 세로)
top : 종유석

bottom : 석순

 

N 제한이 200,000 H 제한이 500,000 으로 단순하게 일일이 비교하는 O(NH) 방식으로는 절대 해결할 수 없다. (20만 * 50만 = 1000억 => 1초안에 불가능)

조금 더 효율적인 방식으로 해결해야 하는데, 종유석과 석순을 구분지어서 생각해 볼 수 있다.

종유석만 보았을 때, 그림에서 높이가 작아질수록(H => 0) 지나가는 종유석이 증가하는 것을 볼 수 있다. 즉 특정 높이 h에서 지나가는 종유석의 개수는 높이 h+1 에서 통과하는 종유석의 개수 + 높이 h에서 새롭게 통과하는 종유석의 개수로 판단할 수 있다. 석순의 경우도 마찬가지이다.

이를 통해 누적 합(Prefix Sum) 으로 해결 할 수 있으며, 시간복잡도 O(N+H) (?) 를 통해 문제를 해결할 수 있다.

 

1. 석순과 종유석을 총 N만큼 입력받으면서, 특정 높이에서 각각의 개수를 하나씩 증가시킨다.

 

2. 각각에 대해 누적합을 구해준다.

- 종유석은 높이가 낮아질수록(H => 0 방향) 통과하는 개수가 증가한다.

- 석순은 높이가 높아질수록(0 => H 방향) 통과하는 개수가 증가한다.

- 특정 높이 h에서 통과하는 종유석의 총 개수는 높이 h + 1에서 통과하는 개수 + 높이 h에서 새롭게 통과하는 종유석의 개수

- 특정 높이 h에서 통과하는 석순의 총 개수는 높이 h - 1에서 통과하는 개수 + 높이 h에서 새롭게 통과하는 석순의 개수

 

3. 석순(bottom)과 종유석(top) 의 누적합을 더해준다.

 

4. 최소값과 구간의 수를 출력한다.

 

코드

import sys

# 석순과 종유석을 나누어서 갯수를 세준다음, 둘을 합쳐서 갯수를 세주는 방식으로 해결 가능하다.

if __name__ == '__main__':
    N, H = map(int, sys.stdin.readline().split())
    top = [0] * (H + 1) # 종유석
    bottom = [0] * (H + 1) # 석순

    for i in range(N):
        num = int(input())
        if i % 2:
            top[num] += 1
        else:
            bottom[H - num + 1] += 1
    # 종유석은 높이 H부터 하나씩 줄여가면서 갯수를 세준다.
    # ex ) 높이가 3일때 길이가 3 이상인 종유석은 반드시 지나가게 되므로 높이를 줄여가면서 누적합(prefix sum)으로 해결할 수 있다.
    for i in range(H - 1, 0, -1):
        top[i] += top[i + 1]
    # 석순은 높이 1부터 하나씩 늘려가면서 갯수를 세준다.
    # ex ) 높이가 3일때 길이가 3 이상인 석순은 반드시 지나가게 되므로 높이를 늘려가면서 누적합(prefix sum)으로 해결할 수 있다.
    for i in range(1, H + 1):
        bottom[i] += bottom[i - 1]
    total = [0] * (H + 1)
    # 각각의 높이에서 석순과 종유석의 누적합 더해주기
    for i in range(1, H + 1):
        total[i] = top[i] + bottom[i]
    # 0번 높이는 삭제
    total = total[1:]
    ans = min(total)
    print(ans, total.count(ans)) # 결과 출력

 

결과

 

문제풀이나 코드에서 이상한 부분 지적은 언제나 환영합니다!