빗물 [백준 14719] - python

import sys
input = sys.stdin.readline

def BOJ14719() :
  H, W = map(int, input().split())
  l = list(map(int, input().split()))

  graph = [[0 for _ in range(W)] for _ in range(H)]
  
  for i in range(H) :
    for j in range(W) :
      if l[j] == H - i :
        graph[i][j] = 1
        l[j] -= 1

  for i in range(H) :
    start = -1
    end = -1

    for j in range(W) :
      if graph[i][j] == 1 :
        if start != -1 :
          end = j
          for k in range(start + 1, end) :
            graph[i][k] = 3
          start = end
          end = 0

        start = j
        

  answer = 0
  for i in range(H) :
    for j in range(W) :
      if graph[i][j] == 3 :
        answer += 1
  print(answer)

BOJ14719()

 

풀이 방식

1. 배열의 인덱스 접근이 어려웠던 문제였다. 

2. 포인터 두개를 사용하였다. 왼쪽에서 오른쪽으로의 탐색을 진행했다.

3. start포인터와 end 포인터 두개가 전부 -1 이 아닐때 포인터 사이의 값들을 빗물로 채워주었다.

4. 벽돌을 인덱스에 맞게 표현해 주는 것과 포인터 두개를 이용하는 개념을 떠올리는 것이 주요했던 문제인것 같다.

 

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

14719번: 빗물