[백준] 14719번 : 빗물 (python 파이썬)

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

 

h,w = map(int, input().split(" "))
l = [[0 for i in range(w)] for j in range(h)]
r = list(map(int , input().split(" ")))
for i in range(w):
   for j in range(r[i]):
    l[h-j-1][i] =1

answer = 0
for i in range(h-1,-1,-1):
    rain = 0
    start = False
    for j in range(w-1,-1,-1):
        if l[i][j] == 1 and start == False: 
            start = True
        elif l[i][j] == 1 and start == True:
            answer += rain
            rain = 0
        elif l[i][j] == 0 and start == True:
            rain+=1
print(answer)

 

해당 문제는 단순한 구현 문제였다. 

 

하지만 어떻게 구현을 하느냐에 따라 문제의 난이도가 매우 달라질 것 같다.

 

처음에 나는 최대한 효율적이고, 최적의 방법을 찾으려 했다.

 

하지만 계산 수를 없에고, 중복을 줄이려고 하면 할 수록 고려해야 할 점이 많아졌고,

경우의 수가 점점 증가하게 되었다.

 

이 문제의 입력의 수는 500으로 매우 작은 편이다.

 

따라서 정말 주어진 대로 구현을 하기로 하였다.

 

for i in range(w):

   for j in range(r[i]):

    l[h-j-1][i] =1

 

해당 for문을 통해서 실제 입력의 값을 그대로 시뮬레이션 하였다.

 

[0, 0, 0, 1]
[1, 0, 0, 1]
[1, 0, 0, 1]
[1, 0, 1, 1]

이런 식으로 실제로 입력값과 같은 모양이 되도록 구현하였다.

 

그리고, 빗물이 쌓이는 방향으로 빗물의 경우를 체크하였다.

 

실제로 비가 오면, 빗물은 아래부터 고이게 된다. 

for i in range(h-1,-1,-1):

    rain = 0

    start = False

    for j in range(w-1,-1,-1):

 

 

따라서, 왼쪽 위부터 오른쪽 아래로 순서대로 for문을 돌리지 않고,

오른쪽 아래에서 왼쪽 위로 거꾸로 돌면서, 실제 빗물처럼 아래방향부터 한줄씩 체크하게 하였다.

 

이렇게 실제 환경을 구현하게 되면, 고려해야 할 변수들이 매우 줄어든다는 것을 느끼게 되었다.