[백준] 2304 파이썬(python) : 창고 다각형

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

2304번: 창고 다각형

 

 

문제가 어려운데 해결방법만 알면 난이도가 낮아진다고 느낀다. NHN에 비슷한 문제가 나왔었다고 한다.

 

문제의 그림을 예시로 들면

 

왼쪽에서 시작해서 가장 큰 높이를 가진 기둥까지의 높이를 전부 더한 값과 오른쪽에서 시작해서 가장 큰 높이를 가진 기둥 직전까지의 높이를 더한 값 두 개를 더하면 정답이 나온다.

즉, 왼쪽은 4+4+6+6+6+6+10 = 42이고 오른쪽은 8+8+8+8+8+8+8 = 56이다.

42 + 56 = 98이 정답이 된다.

 

import sys
n = int(sys.stdin.readline())
wall_list = [0] *1001 #1
max_h, max_h_idx = 0, 0 #2
end_idx = 0 #2
for _ in range(n):
    idx, h = map(int, sys.stdin.readline().split()) #3
    wall_list[idx] = h #4
    if max_h < h: #5
        max_h = h
        max_h_idx = idx
    end_idx = max(end_idx, idx) #6

stack = []
answer = 0
for i in range(max_h_idx+1): #7
    if not stack: #8
        stack.append(wall_list[i])
    else:
        if stack[-1] < wall_list[i]: #9
            stack.pop()
            stack.append(wall_list[i])
    answer += stack[-1] #10

stack = [] #11
for j in range(end_idx, max_h_idx, -1): #12
    if not stack:
        stack.append(wall_list[j])
    else:
        if stack[-1] < wall_list[j]:
            stack.pop()
            stack.append(wall_list[j])
    answer += stack[-1]
print(answer)

 

그림처럼 순서대로 주어지지 않고 입력값이 랜덤으로 주어지기 때문에 end_index가 필요하다.

#1 : 막대의 최대 개수는 1000개라 했으니 1001개로 초기화

#2 : 최댓값의 높이와 그 인덱스를 저장할 변수 선언, end_index선언

#3 : 왼쪽 면의 위치를 idx로 그 idx의 값을 높이로 지정해서 입력값을 받는다

#4 : 입력값 대입

#5 : 한 바퀴 돌면서 최대 높이와 그 최대 높이의 인덱스 저장

#6 : 숫자가 랜덤으로 들어오기 때문에 마지막 인덱스 저장

#7 : 왼쪽에서부터(index 0) 가장 큰 높이의 인덱스까지 돌면서

#8 : stack이 비어 있으면 값을 삽입

#9 : 입력값이 stack에 들어있는 값보다 더 크면 대체

#10 : 대체가 되지 않아도 대체가 되어도 결괏값에 누적해서 stack[-1] 더해줌

#11 : 이젠 오른쪽에서 반복을 돌기 위해 stack 초기화

#12 : end_idx에서부터 -1씩 max_h_idx까지 반복하면서 위와 동일

 

해결방법을 알면 쉽게 풀리고 그렇지 않으면 엄청 어려운 문제 같다. 그래서 고수들이 난이도를 낮게 줘서 실버 2에 넣은 거라고 생각한다. 하지만 별 수 있나 그냥 공부해야지