[BOJ] 14719 - 빗물 (🥇 골드 5티어)

사용 언어: Python3

문제

빗물

풀이

나의 풀이

H, W = map(int, input().split())
lst = list(map(int, input().split()))
visited = [0] * W

tot = 0
for i in range(1, W-1):
    if visited[i] == 1:
        continue
    if lst[i] <= lst[i-1] and lst[i] <= lst[i+1]: # 물이 고일 수 있음 -> pivot은 lst[i]
        # 왼쪽 끝 찾기
        lp = i
        while lp > 0:
            if lst[lp] <= lst[lp - 1]:
                lp -= 1
            else:
                break
        # 오른쪽 끝 찾기
        rp = i
        while rp < W:
            if rp == W - 1: # 맨 마지막 인덱스라면 break
                break
            elif lst[rp] <= lst[rp + 1]:
                rp += 1
            else:
                break

        mn = min(lst[lp], lst[rp]) # 더 낮은 블록 높이
        visited[lp], visited[rp] = 1, 1
        for j in range(lp + 1, rp):
            visited[j] = 1
            tot += (mn - lst[j])
print(tot)

• 테스트 케이스: 통과
• 제출 결과
  

다른 풀이

h, w = map(int, input().split())
blocks = list(map(int, input().split()))

tot = 0
for i in range(1, w - 1):
    left_max = max(blocks[:i])
    right_max = max(blocks[i+1:])

    mn = min(left_max, right_max)

    if blocks[i] < mn: # ✅ 자신보다 더 높은 블록으로 둘러싸여 있다는 의미
        tot += mn - blocks[i]

print(tot)

• 가장 먼저 특정 위치에 물이 고이는지 고이지 않는지를 판단해야 한다.
  • 특정 위치에 물이 고이기 위해서는,
    해당 위치를 기준으로 두 묶음으로 나눴을 때, 각 묶음에 자신보다 더 높은 블록이 존재해야 한다.
• 위 조건을 만족할 때 물이 고이는 양은 (왼쪽 max 블록과 오른쪽 max 블록 중 더 낮은 블록) - (현재 블록의 높이) 이다.
• 첫 번째 칸과 마지막 칸은 물이 고일 수 없으므로 range를 1부터 W-1 까지 잡아준다.

---

💛 개인 공부 기록용 블로그입니다. 👻

맨 위로 이동하기