[#14719] 빗물

문제

#14719 빗물
Silver4
적용 알고리즘: Implementation 알고리즘

---

풀이 방법

• 각 층(행)마다 고이는 물의 양을 계산하여 총 밋물에 더한다.
• 가장 높은 땅 위로는 물이 고일 수 없다.
• 각 층에 대해, 예를 들어 땅의 높이가 3이라면, 높이가 3이상인 땅과 높이가 3이상인 땅 사이에 빗물이 고일 수 있다. -> 즉 높이가 n이상인 땅 사이의 간격을 계산한다.
• 각 층에 대해, 땅을 가로로 순회한다.

코드 흐름

1. 가장 높은 땅의 높이를 구하고 검사할 범위를 지정한다(0~땅의 높이).
2. 특정 땅의 높이(i)보다 같거나 큰 땅의 높이를 가진 땅의 첫 번째 인덱스(idx)를 구한다.
3. idx + 1번째의 땅부터 가로로 순회하면서, 해당 땅의 높이가 특정 땅의 높이(i)보다 낮다면 빗물이 고일 수 있다. count를 하나 증가한다.
4. 만약 같거나 높다면, 이전까지 고인 빗물을 total에 추가하고 현재까지 쌓인 빗물의 수를 0으로 초기화한다.
5. 2~4의 과정을 각 층에 대해 반복한다.

코드

h, w = map(int, input().split())
floor = [int(m) for m in input().split()]

level = max(floor)
total = 0
count = 0

for i in range(0, level + 1):
    idx = 0
    # 첫 번째 인덱스 탐색
    for k in range(w):
        if (floor[k] >= i):
            idx = k
            break
    k = 0
    for k in range(idx + 1, w):
        if (floor[k] < i):  # 빗물 축적
            count += 1
        else:               # 합병
            total += count
            count = 0
    if (k + 1 == w):
        count = 0

print(total)

체감 난이도: 4/5
처음에는 땅에대해서 board등으로 시각화를 하여 문제를 물어야 하나 생각하였지만, 입력 수 만으로도 간단하게 풀 수 있는 문제였다.