158. 창고 다각형

1) 어떤 전략(알고리즘)으로 해결?

2) 코딩 설명

<내 풀이>

• 가장 높은 길이의 인덱스를 만나기 전 : 처음부터 가장 긴애 만나기 전까지, 만약 나보다 큰애 만나면 그 순간 그 사이 넓이 계산
• 가장 높은 길이의 인덱스 : 이 친구의 넓이 (1*높이) 를 결과에 더해줌
• 가장 높은 길이의 인덱스를 만난 후 : 맨 뒤 (맨 마지막) 애부터 돌면서 맨 마지막부터 제일 큰 애 사이에 맨 마지막아이의 높이보다 큰 애가 있는지 검사, 큰애가 있다면 그 사이 넓이 더하기

import sys

n = int(sys.stdin.readline().rstrip())
stk=[]
save=[]
res=0

for i in range(n) :
    save.append(list(map(int,sys.stdin.readline().rstrip().split()))) 

# x축 기준으로 오름차순
save.sort() 

# 오름차순 기준으로, 1,h 말고도 추가로 
# 인덱스를 나타내는 지표도 추가
for i in range(len(save)) :
    save[i].append(i)


# 가장 긴 애의 인덱스 구하기
maxheight=-999
maxidx=0
for i in save:
    if maxheight<i[1] :
        maxheight = i[1]
        maxidx=i[2]

stk.append(save[0])

# 제일 긴 애 만나기 전 (앞에서부터 검사)
for i in range(1,maxidx+1) :
    if stk[-1][1] < save[i][1] : 
        res+=(save[i][0]-stk[-1][0])*stk[-1][1]
        stk.append(save[i])

# 가장 높은 것 만났을 때 
res+=save[maxidx][1]
stk.append(save[maxidx])

# 제일 긴 애 만난 후 (이번엔 뒤에서부터 검사)
stk2=[]
stk2.append(save[-1])

for j in range(n-2, maxidx-1, -1) : 
    if stk2[-1][1] <= save[j][1] : 
        res+=(stk2[-1][0]-save[j][0])*stk2[-1][1]
        stk2.append(save[j])

print(res)

<내 틀렸던 풀이, 문제점>

import sys

n = int(sys.stdin.readline())
stk=[]
save=[]
res=0

for i in range(n) :
    save.append(list(map(int,sys.stdin.readline().split()))) 

save.sort() # x축 기준으로 오름차순

for i in range(n) :
        # l,h 입력들어온 것
    if stk : 
        if stk[-1][1] < save[i][1] : 
            #만약 스택의 마지막 애의 높이보다 내 높이보다 크면
            if i==(n-1) : #마지막 순서애가 젤 크면 얘 넓이 추가적으로 res에 더해야함
                res+=save[i][1]
            res+=(save[i][0]-stk[-1][0])*stk[-1][1]
            stk.append(save[i])

        elif i==(n-1) : # 마지막인데, 위에서 안 걸렸더라면
            # 스택 마지막보다 크지 않지만, 끝내야 하므로
            res+=(save[i][0]-stk[-1][0])*save[i][1]

            # 그리고 제일 컸던 애 넓이 별개 저장 과정
            res+=stk[-1][1] # 1*높이가 걔의 넓이

    else : # 맨 처음에 stk에 넣어두기 
        stk.append(save[i])

print(res)

• 고려하지 않은 예외사항들이 많았다.

import sys

n = int(sys.stdin.readline())
stk=[]
save=[]
res=0

for i in range(n) :
    save.append(list(map(int,sys.stdin.readline().split()))) 

save.sort() # x축 기준으로 오름차순

for i in range(n) :
    save[i].append(i)

for i in range(n) :
        # l,h 입력들어온 것
    
    if stk : 
        if stk[-1][1] < save[i][1] : 
            #만약 스택의 마지막 애의 높이보다 내 높이가 크면
            if i==(n-1) : #마지막 순서애가 젤 크면 얘 넓이 추가적으로 res에 더해야함
                res+=save[i][1]
            res+=(save[i][0]-stk[-1][0])*stk[-1][1]
            stk.append(save[i])

        elif i==(n-1) : # 마지막인데, 위에서 안 걸렸더라면
            # 스택 마지막보다 크지 않지만, 끝내야 하므로
            res+=stk[-1][1] 
            # print("in")
            for j in range(stk[-1][2]+1, save[i][2]) :
                # print("res ", res)
                # print("stk ", stk)
                if save[j][1] > save[i][1] :
                    res+=(save[j][0]-stk[-1][0])*save[j][1]   
                    stk.append(save[j])

            res+=(save[i][0]-stk[-1][0])*save[i][1]  

    else : # 맨 처음에 stk에 넣어두기 
        stk.append(save[i])
        if i==(n-1):
            res+=save[i][1]
    # print("stk ", stk)
    # print("res ", res)

print(res)

• 예외를 고려했는데두 이런다

import sys

n = int(sys.stdin.readline())
stk=[]
save=[]
res=0

for i in range(n) :
    save.append(list(map(int,sys.stdin.readline().split()))) 

save.sort() # x축 기준으로 오름차순
for i in range(len(save)) :
    save[i].append(i)

maxheight=-999
maxidx=0
for i in save:
    if maxheight<i[1] :
        maxheight = i[1]
        maxidx=i[2]

stk.append(save[0])
#전
for i in range(1,maxidx+1) :
    if stk[-1][1] < save[i][1] : 
        res+=(save[i][0]-stk[-1][0])*stk[-1][1]

res+=save[maxidx][1]
stk.append(save[maxidx])
# print("before res ", res)
# print("stk ", stk)
#후
if maxidx<n:

    for j in range(maxidx+1, n-1) :
        if save[j][1] > save[-1][1] :
            # print("res ", res)
            res+=(save[j][0]-stk[-1][0])*save[j][1]
            stk.append(save[j])
    # print('fuck ', ((save[-1][0]-stk[-1][0])*save[-1][1]))
    res+=((save[-1][0]-stk[-1][0])*save[-1][1])

print(res)

• 다른 방식으로 접근해도 틀렸다구 나오내,,,,

테스트케이스를 참고하다가 틀린 테케를 드디어 발견 !
5
1 4
2 5
3 6
4 5
5 4
=> 원래 답 : 24
=> 나의 답 : 27

import sys

n = int(sys.stdin.readline().rstrip())
stk=[]
save=[]
res=0

for i in range(n) :
    save.append(list(map(int,sys.stdin.readline().rstrip().split()))) 

save.sort() # x축 기준으로 오름차순
for i in range(len(save)) :
    save[i].append(i)

maxheight=-999
maxidx=0
for i in save:
    if maxheight<i[1] :
        maxheight = i[1]
        maxidx=i[2]

stk.append(save[0])
#전
for i in range(1,maxidx+1) :
    if stk[-1][1] < save[i][1] : 
        res+=(save[i][0]-stk[-1][0])*stk[-1][1]
        stk.append(save[i])

res+=save[maxidx][1]
stk.append(save[maxidx])

#후
if maxidx<n:

    for j in range(maxidx+1, n-1) :
        if save[j][1] > save[-1][1] :
            # print("res ", res)
            res+=(save[j][0]-stk[-1][0])*save[j][1]
            stk.append(save[j])
    res+=((save[-1][0]-stk[-1][0])*save[-1][1])

print(res)

• 모든 테스트케이스 + 블로그 테스트케이스들 다 통과하는데,,, 반례가 뭔질 모르겠다.

드디어 반례 발견! 😭

https://www.acmicpc.net/board/view/87059
나와 똑같이 8퍼센트에서 틀리는 것까지 god 벽 ,,, 😍 너무 감사해서 절을 드리고 싶다!!!

너무 감사하다..진짜...사랑합니다....

<반성 점>

• 내 코드가 맞는다는 생각에,, 자만해서 제대로 된 반례를 찾지 못했다.

<배운 점>

• 백준에 질문란이 있는지 몰랐다! 앞으로 반례가 필요하면 요기부터 체크하기