14719 빗물

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

#구현

#시뮬레이션

14719번: 빗물

#1 예전에 풀었던 방법

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

#input height by h weight by w
block=list(map(int,input().split()))

#block is a list of the number of arranged blocks

result=0

#creat result
for i in range(1,len(block)-1):
result+=max(0,(min(max(block[:i]),max(block[i+1:]))-block[i]))

'''

we should think 3 important things

1. how many blocks have the largest number on each side?

2. find out what's lower

3. does it have the higher number than the block being compared now?

'''

print(result)

#finish

 

#엄청 쉽게 풀었었다. 물론 인터넷의 도움을 받았겠지만 이 시간을 더 줄일 수 있을지를 더 찾아보았고 찾게 되었다.

 

#2 현재 푼 방법

#14719 빗물 정리

h,w=map(int,input().split())
#height:h width:w

 

block=list(map(int,input().split()))
#the list of arranged block

 

long=max(block)
#the largest number of blocks

 

ans= h*w - sum(block)
#we first need to know the total area minus the number of blocks.

 

if long != h:

ans-=(h-long) * w
#if miximum height is smaller than the largest number of blocks we need to subtract h minus long multiplied by c from ans

for i in range(w):

if block[i]==long:

l=i

break

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

if block[j]==long:

r=j

break

#we need to find index values for the largest number of blocks on both sides.

 

l_index=l
r_index=r

l_max=long
r_max=long

#store each index value and maximum value.

 

while l_index>0:

l_sub_block=block[:l]
l_sub_max=max(l_sub_block)
for i in range(l-1,-1,-1):
if block[i]==l_sub_max:
index=i
break
ans-=(l_max - l_sub_max)*l
if index==0:
break
l=index
l_max=l_sub_max

while r_index < w-1:

r_sub_block=block[r+1:]
r_sub_max=max(r_sub_block)
for i in range(r+1,w):
if block[i]==r_sub_max:
index=i
break
ans-=(r-max - r_sub_max) * (w-1-r)
if index==w-1:
break
r=index
r_max=r_sub_max
print(ans)

# firstly we got the width of the block at its maximum height and we also got index values and maximum values for the largest number of blocks on both sides.
# now we should subtract blocks from the width with idea of cutting the height by little and little
# find the highest value except i for each direction and store its index value and that value
# and if that value is not in other lower(l) index value find the number of l_max minus l_sub_max
# subtract that number multiplied by l_index minus l_sub_index from total area from 0 to l_index
# if that value is in other lower index change l_max and l to l_sub_max and l_sub_index
# ans would be the answer

 

#3 1번째 정리 한글

 

#14719 빗물

h,w=map(int,input().split())
#h,w 입력
block=list(map(int,input().split()))
#블록 가져오기
thelonggest=max(block)
#블록에서 가장 높은 값
result=thelonggest*w-sum(block)
#블록에서 가장 높은 값에 너비를 곱하고 다 담을 수 있다는 가정하에 합계를 뺀다
for i in range(w):

    if block[i]==thelonggest:

        l=i

        break

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

    if block[j]==thelonggest:

        r=i

        break
# 양쪽에서부터 봐서 가장 높은 인덱스를 찾자
l_max=thelonggest
r_max=thelonggest

while l>0:

    l_sub_max=max(block[:l])

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

        if block[i]==l_sub_max:

            index=i

            break

    result-=(l_max-l_sub_max) * l

    l=index
    l_max=l_sub_max

while r<w-1:

    r_sub_max=max(block[r+1:])

    for j in range(r+1,w):

        if block[j]==r_sub_max:

            index=j

            break

    result-=(r_max-r_sub_max)*(w-1-r)

    r=index
    r_max=r_sub_max

#생각해야되는건 가장 높은 블록 말고 두번째로 높은 블록을 기준으로 채워진다는 것이다 304면 3까지만 물이 담겨지는 원리이다. 고로 두번쨰로 높은 블록들을 찾고 그것의 인덱스 값을 내리면서 찾는다. 그 후 두번째로 높은 블록과 가장 높은 블록 그 사이에 있는 물들을 빼준다 이게 이제 result-=(thelonggest-l_sub_max) * l 이렇게 되는것이다. 생각하기 힘들긴 한데 아까 이미 있다고 생각하고 물을 옆에 머가 있든 일단 사각형모양으로 다 채워놨다고 생각하면 편하다
print(result)

 

#3 2번째 정리

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

height=0

blocks=list(map(int,input().split()))

for i in range(w):

    if height< blocks[i]:

        max_index=i

        max_height=blocks[i]

result=0

block=0

for i in range(max_index+1):

    if blocks[i]>block:

        block=blocks[i]

    result+=block

block=0

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

    if blocks[j]>block:

        block=blocks[j]

    result+=block

print(result-sum(blocks))

# 이것도 비슷한 알고리즘 가장 높은 값 찾고 그것의 인덱스를 찾은 후 그것의 양옆에서부터 봐서 거기서 이제 가장 높은 값을 찾는 것이다. 다른 것은 이제 하나씩 찾아서 그쪽부터 팔을 뻗듯이 뻣어나가는 것이 1번째이지만 2번째는 하나를 찾아서 그쪽까지 팔을 오므리듯이 찾아주는 것이다.

 

#힘들었고 힘들었다. 이번에 카카오문제에 나왔다고 하더라 나도 코테 잘하고싶다