백준 14719 빗물 파이썬 풀이 2가지 경우 고려하자 구현문제

빗물 성공

 

 

시간 제한메모리 제한제출정답맞힌 사람정답 비율

1 초

256 MB

14370

8025

6311

55.983%

문제

2차원 세계에 블록이 쌓여있다. 비가 오면 블록 사이에 빗물이 고인다.

비는 충분히 많이 온다. 고이는 빗물의 총량은 얼마일까?

입력

첫 번째 줄에는 2차원 세계의 세로 길이 H과 2차원 세계의 가로 길이 W가 주어진다. (1 ≤ H, W ≤ 500)

두 번째 줄에는 블록이 쌓인 높이를 의미하는 0이상 H이하의 정수가 2차원 세계의 맨 왼쪽 위치부터 차례대로 W개 주어진다.

따라서 블록 내부의 빈 공간이 생길 수 없다. 또 2차원 세계의 바닥은 항상 막혀있다고 가정하여도 좋다.

출력

2차원 세계에서는 한 칸의 용량은 1이다. 고이는 빗물의 총량을 출력하여라.

빗물이 전혀 고이지 않을 경우 0을 출력하여라.

예제 입력 1 복사

4 4
3 0 1 4

예제 출력 1 복사

5

예제 입력 2 복사

4 8
3 1 2 3 4 1 1 2

예제 출력 2 복사

5

예제 입력 3 복사

3 5
0 0 0 2 0

예제 출력 3 복사

0

힌트

힌트 1:

힌트 2:

힌트 3:

 

 

 

 

h, w =map(int, input().split())
arr=[]
arr=list(map(int, input().split()))

s_idx=0

for i in range (w):
    if arr[i]!=0:
            s_idx=i #시작 인덱스구하기
            break
            
temp=[]
water=0
top=0
top_idx=0
i=s_idx+1

while(i<w):
    if arr[s_idx] > arr[i] :# 기준보다 낮은 경우 
        temp.append(arr[i])
        if(top <= arr[i]):
            top=arr[i] #높은 기둥 갱신
            top_idx=i
    else: #같거나더 높은 경우, 구하기
        if(top<=arr[i]):
            top=arr[i] #높은 기둥 갱신
            top_idx=i
        if (s_idx!=top_idx):
            k=(min(arr[s_idx], top))*(top_idx-s_idx-1) -sum(temp[0:top_idx-s_idx-1])
            water+=k
            #print(s_idx, top_idx, k, water)
        s_idx=top_idx
        temp=[]
        top=0
        top_idx=0
            
    if i+1 == w:#끝까지 온 경우
        if(top!=0): #top이 생성되었다면 거기까지 구하기
            k=(min(arr[s_idx], top))*(top_idx-s_idx-1) -sum(temp[0:top_idx-s_idx-1])
            water+=k
            #print(s_idx, top_idx, k, water)
            s_idx=top_idx
            i=s_idx-1
            temp=[]
            top=0
            top_idx=0
            
    i+=1
    
print(water)

어떻게 풀면 좋을까? 종이에 그림을 그리면서 풀었다 

빗물이 고이는 경우는 이러하다

1. 기준 기둥보다 같거나 높은 기둥을 만날때

2. 기준 기둥보다 낮은 기둥을 만날때로, 기준 기둥부터 공간의 끝까지 기준 기둥보다 큰 기둥을 만나지 못하는 경우이다.  

 

1번의 경우는 구하기 쉽지만(코드의 while문의 else)

2번의 경우는 낮은 기둥 중 무엇을 선택해야하는지 고려해야한다!! 

따라서 top기둥을 설정해 기준 기둥 다음의 가장 높은 기둥을 저장하고, 끝에 도달하였을 때  

top기둥까지 구하고, top기둥을 다시 기준 기둥으로 재설정후 반복문을 돌면 고인 빗물을 모두 구할 수 있다. 

그림으로 설명해보면 

퀄리티 지송..

위와같이 4x7의 모양의 공간에 

3 0 0 2 0 1 0 

의 기둥크기를 입력받는 예제가 있다고 했을 때 

 

 

고인 빗물은 다음과 같이 파란 부분으로 총량은 4+1로 5일 것이다. 

저 부분을 구해보자!! 

 

먼저 기둥 크기가 0이 아닌 점을 찾아 시작 인덱스 s_idx로 설정하고, 

top기둥의 크기를0, top_idx를 0으로 설정한다.

temp=[]는 빗물이 고이는 곳들의 기둥의 크기를 저장한다. 

while문에서 

s_idx기둥보다 i기둥의 크기가 작다면 temp에 기둥 크기를 append해주고, 

만약 i기둥크기가 top기둥보다 크다면(낮은 기둥 중 가장 크다) top을 i로 갱신해준다.

만약 s_idx기둥보다 i 기둥의 크기가 크거나 같으면 1번 케이스로, 우선 top기둥을 i로 갱신하고

s_idx와 i_idx가 같지 않은 경우에만(여기 설정안하면 k에서 -값을 구해서 오류난다) 고인물 k를 계산해 water에 추가한다. 

여기까지가 1번 케이스고,

이제 2번 케이스인 경우는 아까말했듯이 기준 기둥에서 끝까지 갔을 때 기준 기둥보다 큰 기둥이 없는 경우이다.

그러니까 이경우에는 i가 w-1인 경우일 것이다.

따라서 if문으로 이 경우를 캐치해서

top이 0이라면 어떠한 top기둥이 설정되지 않았다는 것이니까, 기둥이 아예 없었다는 뜻이다. 따라서 빗물이 고이지 않음!

top이 0이 아닐 때만 구해주면 된다. 마찬가지로 top기둥까지 빗물 양 k를 구해주고

나머지 변수를 초기화하고, i를 top_idx-1로 설정해야한다(-1인 이유는 while문에서 i에 1 더해주기 때문에)

이렇게 기준 기둥을 갱신하고 다시 while문을 돌면서 구하는 것이다. 

 

그렇게하면 

처음에는 s_idx=0, top_idx=3이기 때문에

공간을 끝까지 도달했을 때 top인덱스만큼의 4만큼 크기를 구하고, i를 다시 top기둥으로 갱신해서

s_idx=3, top_idx=5가 되기 때문에

공간을 다시 끝까지 도달해 top인덱스만큼의 1만큼 크기를 구하여 

water는 5로 구해진다!!

 

 

 

그리고 i를 갱신하는 과정에서

파이썬에서 for문의 i값을 임의로 조정하는 것을 불가능하다는 것을 알게되어서

while문으로 변경하여 i를 유동적으로 바꾸어 기준기둥을 갱신하며 고인 빗물을 계산하였다.