매일 문제 풀이

1. 빗물(백준 14719)

벽의 모양이 주어지면 담길 수 있는 빗물의 칸 수를 출력하는 문제.
2차원 정보로 주어졌다면 아래에서 부터 행마다 둘러싸인 칸 수만을 더하면 된다.
하지만 문제는 특이하게 벽의 정보가 2차원으로 주어지지 않고 왼쪽부터 벽의 높이로 주어지므로 다른 방법을 찾아야 한다.
즉, 벽은 중간이 빌 수 없고 바닥에 붙어있다.

왼쪽부터 벽을 점검하며 벽이 높아지는 순간 이전 열들에 물을 채워넣는 방식으로 구현했다.

def main() -> None:
    H, W = map(int, input().split())
    WALL = list(map(int, input().split()))

    answer = 0
    idx_max = 0
    for i in range(1, W):
        if WALL[i] > WALL[i-1]:
            for j in range(i-1, idx_max, -1):
                if WALL[j] >= WALL[i]:
                    break
                answer += min(WALL[idx_max], WALL[i])-WALL[j] # 실수 2를 고친 부분
                WALL[j] = min(WALL[idx_max], WALL[i]) # 실수 1을 고친 부분
            if WALL[i] >= WALL[idx_max]:
                idx_max = i

    print(answer)

if __name__ == "__main__":
    main()

구현 중 실수:

1. 벽이 높아지면 이전 최대 높이의 벽까지 다 채워버렸다.
   예를 들어 4 3 1 2이면 마지막에 벽이 높아지므로 물을 채워 4 3 2 2 형태로 만들어야 한다.
   하지만 그냥 4 2 2 2로 만들어버렸다.
2. 현재 벽 높이 기준으로 일괄 물을 채워버렸다.
   3 2 1 4이면 3높이까지만 채워 3 3 3 4로 만들어야 하는데 4 4 4 4로 만들어 버렸다.

그냥 2차원 배열로 만들어 버릴까

벽의 개수가 최대 500개이기 때문에 제한시간이 넉넉하다.
그냥 2차원 배열로 풀어봤다.

def main() -> None:
    H, W = map(int, input().split())
    WALL = list(map(int, input().split()))

    answer = 0
    arr = []
    for wall in WALL:
        arr.append([1 for _ in range(wall)] + [0 for _ in range(H-wall)])

    for i in range(H):
        last = -1
        for j in range(W):
            if arr[j][i] == 0:
                if last != -1:
                    last += 1
            else:
                if last != -1:
                    answer += last
                last = 0
    print(answer)

if __name__ == "__main__":
    main()