[Gold V] 빗물 - 14719

문제 링크

성능 요약

메모리: 32412 KB, 시간: 68 ms

분류

구현, 시뮬레이션

문제 설명

2차원 세계에 블록이 쌓여있다. 비가 오면 블록 사이에 빗물이 고인다.

비는 충분히 많이 온다. 고이는 빗물의 총량은 얼마일까?

입력

첫 번째 줄에는 2차원 세계의 세로 길이 H과 2차원 세계의 가로 길이 W가 주어진다. (1 ≤ H, W ≤ 500)

두 번째 줄에는 블록이 쌓인 높이를 의미하는 0이상 H이하의 정수가 2차원 세계의 맨 왼쪽 위치부터 차례대로 W개 주어진다.

따라서 블록 내부의 빈 공간이 생길 수 없다. 또 2차원 세계의 바닥은 항상 막혀있다고 가정하여도 좋다.

출력

2차원 세계에서는 한 칸의 용량은 1이다. 고이는 빗물의 총량을 출력하여라.

빗물이 전혀 고이지 않을 경우 0을 출력하여라.

---

문제 풀이

문제 분석

이 문제는 2차원 세계에 블록이 쌓여 있을 때, 비가 온 후 고이는 빗물의 총량을 계산하는 문제입니다. 입력으로는 세계의 세로 길이 H, 가로 길이 W, 그리고 각 위치의 블록 높이가 주어집니다. 출력은 고이는 빗물의 총량입니다.

접근 방법

이 문제는 시뮬레이션 방식으로 해결할 수 있습니다. 각 높이 레벨별로 물이 고일 수 있는지 확인하고, 고일 수 있다면 해당 영역의 넓이를 계산하여 총 빗물 양에 더합니다. 즉, 1부터 H까지 각 높이에 대해, 왼쪽에서 오른쪽으로 탐색하며 현재 높이 이상의 블록을 만나면 빗물이 고이기 시작했음을 표시하고, 다시 현재 높이 이상의 블록을 만나면 그 사이의 빈 공간에 빗물이 고인 것으로 계산합니다.

구현 설명

1. 입력 받기

• 첫 번째 줄에서 H와 W를 입력받고, 두 번째 줄에서 각 위치의 블록 높이를 리스트 graph로 입력받습니다.

2. 높이 레벨별 탐색

• 1부터 H까지 각 높이 i에 대해 반복합니다.

3. 빗물 고임 여부 확인 및 계산

• start 변수를 False로 초기화합니다. 이 변수는 현재 높이 i에서 빗물이 고이기 시작했는지 여부를 나타냅니다.
• cnt 변수를 0으로 초기화합니다. 이 변수는 현재 높이 i에서 빗물이 고이기 시작한 후, 다음 블록을 만나기 전까지 빈 공간의 수를 카운트합니다.
• graph 리스트를 순회하며 각 위치 j에 대해 다음을 수행합니다.
  • 만약 graph[j]가 현재 높이 i 이상이면:
    • 만약 start가 False이면, start를 True로 설정하고 cnt를 0으로 초기화합니다. 이는 현재 높이에서 처음으로 블록을 만났음을 의미합니다.
    • 만약 start가 True이면, rain에 cnt를 더하고 cnt를 0으로 초기화합니다. 이는 빗물이 고인 영역을 찾았음을 의미합니다.
  • 만약 graph[j]가 현재 높이 i 미만이고 start가 True이면, cnt를 1 증가시킵니다. 이는 빗물이 고일 수 있는 빈 공간을 카운트하는 것입니다.

4. 결과 출력

• 모든 높이에 대해 탐색이 끝나면, rain에 저장된 총 빗물 양을 출력합니다.

⏱복잡도 분석

• 시간 복잡도: O(H*W) 입니다. 1부터 H까지 각 높이에 대해 W번 반복문을 수행하므로, 시간 복잡도는 H와 W의 곱에 비례합니다.
• 공간 복잡도: O(W) 입니다. 블록의 높이를 저장하는 graph 리스트의 크기가 W에 비례합니다. 그 외 변수들은 상수 공간을 사용합니다.

핵심 포인트

1. 높이별 탐색: 각 높이 레벨별로 빗물이 고이는지 확인하는 것이 핵심입니다.
2. start 변수: 빗물이 고이기 시작했는지 여부를 추적하는 start 변수를 사용하는 것이 중요합니다.
3. cnt 변수: 빗물이 고일 수 있는 빈 공간을 카운트하는 cnt 변수를 활용하여 효율적으로 빗물 양을 계산합니다.

풀이 코드

import sys

n, m= map(int,sys.stdin.readline().split())

graph = list(map(int,sys.stdin.readline().split()))

rain = 0
for i in range(1,n+1):
    start = False
    for j in range(m):
        if graph[j] >= i:
            if not start:
                start = True
                cnt = 0

            else:
                rain += cnt
                cnt = 0

        
        if graph[j] < i and start:
            cnt += 1

print(rain)