BJ_ 14719 빗물

문제 링크

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

14719번: 빗물

---

문제  설명/ 풀이

정답률도 55퍼이고 그냥 보기엔 쉬워보였는데, 코드를 짜다보니 반례가 많이 생겨서 생각보다 시간이 엄청 오래 걸렸다

 

고려해야할 조건

1. 물은 양쪽에 기둥이 있을 때 채워진다

위의 그림과 같은 경우 물이 채워지지 않는다

 

2. 양 기둥의 높이가 다를경우 낮은 기둥의 높이에 맞춰 물이 채워진다

가설-1: 양 기둥은 감소배열의 최대값과 증가배열의 최대값이다

-> 2번 조건에 따라 감소배열의 최대값과 증가배열의 최대값 중 최소길이에 맞춰 물이 채워진다

ex.

기준이 첫번째 길이 3짜리 기둥이라면,

감소함수: [3,1] => max =3

증가함수: [1,2,3,4] => max = 4

=> 물이 채워지는 높이 == 2

 

반례-1:

감소함수: [3,1] => max =3

증가함수: [1,2] => max = 2

=> 물이 채워지는 높이 == 2

하지만 전체 그림으로 봤을 때 물이 채워지는 높이는 3이다

 

가설-2: 기준이 되는 기둥의 크기보다 크거나 같은 경우에만 반대쪽 기둥이 될 수 있다

ex.

기준 기둥의 높이: 3

반대쪽 기둥 후보:[3]

==>물이 채워지는 높이 3

 

반례-2:

기준기둥이 길이가 4인 기둥일때, 배열이 끝날때까지 기둥의 크기보다 크거나 같은 경우가 나오지 않는다

 

3. 기준기둥보다 크거나 같은 경우가 없는 경우 기준기둥 다음 배열의 최대값을 물이 채워지는 높이로 한다

ex. 반례 2의 경우

길이가 4인 기둥 이후 4보다 크거나 같은 기둥이 나오지 않았으므로 나머지중 최대값인 2를 반대기둥으로 삼는다

==> 물이 채워지는 높이 2

 

반례-3:

길이가 4인 기둥이 기준일 때 나머지 배열 중 최대값은 3이다.

가정 3에 따르면 물이 채워지는 높이가 3이어야 하지만

하지만 3 이후의 블럭들은 물높이 2로 채워진다

 

가정 - 4:

기준이 되는 기둥의 크기보다 크거나 같은 경우가 없는 경우

나머지 배열 중 최대값이 되는 블럭까지는 물의 높이가 최대값이고

나머지 배열은 새로운 문제로 정의한다

재귀를 통해 또 다른 작은 문제 하나로 생각

 

$\therefore$

1. 기준이 되는 기둥의 크기보다 크거나 같은 경우에는 기준이 되는 기둥의 크기로 물 높이를 채운다

2. 기준이 되는 기둥의 크기보다 크거나 같은 경우가 없는 경우, 나머지 배열의 최대값까지는 최대값으로 물 높이를 채운다

3. 최대값 기둥 이후의 배열은 새로운 작은 문제로 정의한다

---

코드

import sys
a,b = map(int, sys.stdin.readline().rstrip().split()) # 세로, 가로
l = list(map(int, sys.stdin.readline().rstrip().split())) # 기둥 리스트

water = 0 # 빗물 개수

# 빗물 세기
# m은 채워지는 물높이
def water_cal(m, tmp):
    total = 0
    if tmp:
        for i in tmp:
            total = total + m - i

    return total

def solution(b, l):
    idx = 0
    stan = l[idx] # 기준 기둥
    tmp = [] # 기준 기둥보다 작은 경우 tmp에 넣는다
    water = 0 # 채워진 물의 개수

    
    while (idx != b):
        idx = idx + 1 # idx를 한칸씩 증가시키면서 비교
        

        if (idx == b):
            # 인덱스를 끝까지 갔는데, 기준 기둥보다 크거나 같은 경우가 안나온 경우
            if tmp:
                stan = max(tmp) # 나머지 배열의 최댓값을 물의 높이로 잡고
                max_idx = tmp.index(stan)
                water += water_cal(stan, tmp[:max_idx]) # 최댓값기둥 이전의 배열은 물높이를 최대값으로 하여 물을 세준다
                last = tmp[max_idx:] # 최대값 이후의 배열은 작은 문제로 정의하고 solution에 넣어준다
                water += solution(len(last), last)
            continue
            
        # 기준 기둥보다 작은 경우 tmp에 넣기
        if (stan > l[idx]):
            tmp.append(l[idx])
        # 기준 기둥보다 크거나 같은 경우
        else:
            water += water_cal(stan, tmp) # 여기까지 물의 개수를 세주고
            stan = l[idx] # 기준 기둥보다 크거나 같은 경우를 새로운 기준 기둥으로 삼는다
            tmp = [] # 배열 초기화

    return water

print(solution(b,l)) # 채워지는 물의 개수 세기

---

다른 사람의 풀이

h, w = map(int, input().split())
world = list(map(int, input().split()))

ans = 0
# 처음과 마지막은 물이 채워질 수 없음
for i in range(1, w - 1):
    left_max = max(world[:i]) # 왼쪽에서 가장 높은 기둥
    right_max = max(world[i+1:]) # 오른쪽에서 가장 높은 기둥

    compare = min(left_max, right_max) # 기둥 중에 최솟값

	# 자기 자신이 더 크면 물이 안채워짐
    if world[i] < compare:
        ans += compare - world[i] # 물 채우기

print(ans)

물은 기준과 기준 사이에 채우는 것이 아니라, 각 칸마다 채웠다....;;;

천재인가 봄

조건

1. 특정 위치에 물이 고이기 위해선 자신보다 더 높은 블록으로 왼쪽과 오른쪽이 둘러싸여 있어야한다.

 

다음에는 문제를 좀더 작은 단위로 분해해서 생각해보자