[백준] 14719 빗물

📖 문제

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

💻 내 코드

import sys

h, w = map(int, sys.stdin.readline().split())

mlist = list(map(int, sys.stdin.readline().split()))
block = [[0] * w for _ in range(h)]

for i in range(w):
    for j in range(mlist[i]):
        block[j][i] = 1
cnt = 0
for i in range(h):
    mx = 0
    mn = 0
    if 2 <= block[i].count(1) < w:
        for x in range(w):
            if block[i][x] == 1:
                mn = x
                break
        for y in range(w - 1, -1, -1):
            if block[i][y] == 1:
                mx = y
                break
        for k in range(mn, mx + 1):
            if block[i][k] == 0:
                cnt += 1

print(cnt)

💡 풀이

• 블록을 배열로 구현함
• 블록이 있는 곳은 1, 없는곳은 0으로 표현해줌

예를 들어 아래의 그림에서 블록을 그려본다면

(내가 짠 코드는 블록이 위에서부터 그려짐)

이 때 물이 고이는 곳은 1과 1사이의 0이다

for i in range(h):
    mx = 0
    mn = 0
    if 2 <= block[i].count(1) < w:
        for x in range(w):
            if block[i][x] == 1:
                mn = x
                break
        for y in range(w - 1, -1, -1):
            if block[i][y] == 1:
                mx = y
                break
        for k in range(mn, mx + 1):
            if block[i][k] == 0:
                cnt += 1

• 먼저 한 줄에 1이 2개 이상이고 w보다 작은지 확인한다
• 만약 그렇다면 가장 먼저 나오는 1의 인덱스 저장
• 뒤에서부터 계산했을 때 가장 먼저 나오는 1의 인덱스 저장
• 가장 작은 1의 인덱스부터 가장 큰 1의 인덱스 사이에 있는 0의 개수 count
• 최종 개수 출력