[n14719] 빗물 in python

---

(처음 든 생각)

일단 맵을 만들자.

그리고 나서 생각을 다시 해보자,

 

빗물이 차오르게 하려면?

양 옆에 빗물을 가둘 수 있는 기둥이 존재해야 한다.

위 그림에서는 양 옆에 빗물을 가둘 수 있게끔 기둥이 존재하고,

왼쪽 기둥은 높이가 3, 오른쪽 기둥높이는 4이다.

이때는 왼쪽 기둥의 높이에 맞춰야한다. (즉 최솟값)

 

그래서 이때 든 생각은

바닥부터 탐색을 시작해서

체크를 하자..?

---

여기서도 마찬가지로 왼쪽 빗물부터 보면,

왼쪽 기둥 높이는 3, 오른쪽 기둥 높이는 4

이때도 3을 선택

오른쪽 빗물은 왼쪾 기둥이 4, 오른쪽 기둥 높이가 2

따라서 2를 선택

---

위 그림에서는 빗물이 고일 수가 없다.

기둥이 1개만 존재하기 때문이다.

 

---

(내가 맨 처음에 성공했던 풀이)

맨 아래부터 탐색을 시작한다.

h, w = map(int, input().split())  # 행,열
array = [[0 for _ in range(w)] for i in range(h)]
b_h = list(map(int, input().split()))
for i in range(w):
    if b_h[i] == 0:
        continue
    for j in range(b_h[i]):
        array[h - 1 - j][i] = 1

 2차원 배열로 블록이 채워져있는 공간은 1, 비어있는 칸은 0으로 맵 초기화

 

 

---

# 탐색 시작
answer = 0 # 최종값

for i in range(h - 1, -1, -1): #h-1행부터 0행까지 탐색
    start = 0 # start 블록
    end = 0 # end 블록
    num = 0 # 중간중간 빗물 담는 변수

    for j in range(w): # 0행부터 w-1행까지 탐색
        if start == 0: 
            if array[i][j] == 1:
                start = 1
                continue
        else:
            if end == 0:
                if array[i][j] == 0:
                    if j == w - 1:
                        continue
                    num += 1
                    continue
                else:
                    end = 1
                    answer += num
                    num = 0
                    continue
            else:
                if array[i][j] == 1:
                    continue
                else:
                    end = 0
                    num += 1
    if start == 1 and end == 0:
        num = 0
    else:
        answer += num
print(answer)

 

■□□□■를 예시로 들어보면,

맨 앞에 있는 ■가 start

 맨 뒤에 있는 ■가 end

 

만약 빗물 앞에 오는 ■가 없는 상황에 현재 위치에 ■가 있을 경우

-> start=1

 

start=1, 즉 앞에 ■가 있는 경우

만약 뒤에 와야 하는 ■가 없을 경우

계속 빗물을 넣는다. ■가 나올때까지

끝까지 다 왔는데 ■가 없다면? 방금 셋던 값은 answer에 넣지 않는다.

 

만약 현재 위치에 ■가 있을 경우 (end)

-> end=1

answer에 좀전까지 세고 있었던 빗물수를 넣고,

num값은 다시 초기화해준다.

 

만약 end=1인 경우, 

현재 위치에 ■가 있으면 continue

: ■□■(■■)□□■ , 괄호친 부분임

 

■가 없으면, end=0으로 초기화, num+=1 

: ■□■(□)□■. 괄호친 부분임

 

해당 행의 탐색을 마친 후,

만약 start값은 1인데, end가 0인 경우

방금 계산했던 num값이 쓰레기라는 뜻.

예를 들면, ■□□□□□였는데 □의 개수가 num에 있다는 뜻!

그러니 5개는 answer값에 포함되면 안된다.

 

start==1이고 end==0이 아니면,

answer+=num

 

---

전체코드

# 2차원 배열로 블록이 채워져있는 공간은 1, 비어있는 칸은 0으로 맵 초기화
h, w = map(int, input().split())  # 행,열
array = [[0 for _ in range(w)] for i in range(h)]
b_h = list(map(int, input().split()))
for i in range(w):
    if b_h[i] == 0:
        continue
    for j in range(b_h[i]):
        array[h - 1 - j][i] = 1


# 탐색 시작
answer = 0 # 최종값

for i in range(h - 1, -1, -1): #h-1행부터 0행까지 탐색
    start = 0 # start 블록
    end = 0 # end 블록
    num = 0 # 중간중간 빗물 담는 변수

    for j in range(w): # 0행부터 w-1행까지 탐색
        if start == 0: 
            if array[i][j] == 1:
                start = 1
                continue
        else:
            if end == 0:
                if array[i][j] == 0:
                    if j == w - 1:
                        continue
                    num += 1
                    continue
                else:
                    end = 1
                    answer += num
                    num = 0
                    continue
            else:
                if array[i][j] == 1:
                    continue
                else:
                    end = 0
                    num += 1
    if start == 1 and end == 0:
        num = 0
    else:
        answer += num
print(answer)

---

(인터넷에서 찾아본 풀이 참고)

현재 위치를 기준으로 왼쪽과 오른쪽에서 가장 큰 값을 각각 left,right 변수에 저장

left와 right 중 가장 작은 값이 만약 현재 위치의 블록개수보다 작다면?

-> cnt+=min(left,right)-array[i] : 최종 빗물개수

min(left,right) = 3

현재 위치 값 array[i]=1

cnt+=3-1=2

 

 

array[i]>min(left,right)

-> 빗물이 들어갈 공간이 없으므로 continue

 

 

h, w = map(int, input().split())  # 세로,가로
array = list(map(int, input().split()))
cnt = 0

for i in range(0, len(array)):
    left = max(array[:i + 1])
    right = max(array[i:])

    if array[i]>min(left,right):
        continue
    else:
        cnt+=min(left,right)-array[i]

print(cnt)