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

 

문제

 

 

2304번: 창고 다각형

 

정답 소스코드 (Python)

 

n=int(input())
arr=[]
for i in range(n):                  #입력받기
    l,h=input().split()
    arr.append([int(l),int(h)])

arr.sort()                 #정렬
arr_max,arr_max_index=0,0

for i in range(n):                          #최댓값 찾기
    if arr_max<arr[i][1]:
        arr_max=arr[i][1]           #최댓값 저장
        arr_max_index=i             #최댓값 인덱스 저장

high_x,high_y=arr[0][0],arr[0][1]           #초기화
result=0

for i in range(1,arr_max_index+1):  #최댓값과 최댓값 전까지
    if high_y<arr[i][1]:
        result+=(arr[i][0]-high_x)*high_y
        high_x,high_y=arr[i][0],arr[i][1]


result+=arr[arr_max_index][1] #최댓값 추가
high_x,high_y=arr[n-1][0],arr[n-1][1]
for i in range(n-1,arr_max_index-1,-1):
    if high_y<=arr[i][1]:
        result+=(high_x-arr[i][0])*high_y
        high_x,high_y=arr[i][0],arr[i][1]

print(result)

 

 

풀이  (Python)

 

 

이 문제는 생각보다 예외처리가 많은 방식으로 풀이하였다. 필자의 풀이가 좋은 풀이는 아니지만, 막상 이 문제를 처음 봤을 때 처음으로 생각난 로직대로 풀이해 보았다.

 

Point 1)  기본 로직

 

 

 

이와 같은 지붕의 형태를 보고 첫 번째로 떠올릴 수 있는 로직은 최댓값 좌 우로 계단식으로 점차 증가해 오면서 최댓값에서만 우뚝 솟아 있는 형식이라고 생각하였다. 하지만 이렇게 생각한 경우 여러 가지의 생각해야 하는 포인트들이 존재한다. 해당 케이스는 아래와 같다. 

 

 

 

                               (1)                                                             (2)                                                            (3)

 

 

(1) case의 경우 최댓값이 맨 앞쪽에 있는 경우, (2) case의 경우 최댓값이 맨 뒤쪽에 있는 경우, (3) case의 경우 최댓값이 여러 개인 경우이다.

 

 

n=int(input())
arr=[]
for i in range(n):                  #입력받기
    l,h=input().split()
    arr.append([int(l),int(h)])

arr.sort()                 #정렬

 

첫 코드 부분은 n을 입력받고 arr는 이중배열 구조로 x좌표와 y좌표(=높이)를 입력받았다. 이후 정렬하였다.

 

 

arr_max,arr_max_index=0,0

for i in range(n):                          #최댓값 찾기
    if arr_max<arr[i][1]:
        arr_max=arr[i][1]           #최댓값 저장
        arr_max_index=i             #최댓값 인덱스 저장

 

두 번째 코드 블럭은 arr에서의 최댓값을 찾기 위하여 arr_max와 arr_max_index를 초기화 한 이후 for문을 통해 arr에서 최댓값을 찾았다.

 

 

high_x,high_y=arr[0][0],arr[0][1]           #초기화
result=0

for i in range(1,arr_max_index+1):  #최댓값과 최댓값 전까지
    if high_y<arr[i][1]:
        result+=(arr[i][0]-high_x)*high_y
        high_x,high_y=arr[i][0],arr[i][1]

 

 

 

세 번째 코드 블럭은 왼쪽과 같이 최댓값 이전까지의 계단형식으로 해당 지붕 밑의 직사각형 넓이를 구해서 result에 더해 주었다.

 

이를 통해 문제의 기본 예제와 (2) case를 해결할 수 있다.

 

 

 

 

result+=arr[arr_max_index][1] #최댓값 추가


high_x,high_y=arr[n-1][0],arr[n-1][1]
for i in range(n-1,arr_max_index-1,-1):
    if high_y<=arr[i][1]:
        result+=(high_x-arr[i][0])*high_y
        high_x,high_y=arr[i][0],arr[i][1]

 

 

네 번째 코드 블럭은 첫 줄의 최댓값 기둥을 더해준 이후 반복문을 통해 앞서 세 번째 코드블럭과 유사하게 arr의 맨뒤부터 최댓값 인덱스까지 계단형식으로 해당 지붕 밑의 직사각형 넓이를 구하여 result에 더해주었다.

 

이를 통해 문제의 기본 예제와 (1) case를 해결할 수 있다.

 

 

 

 

그럼 (3) case는 어떻게 해결해야 할까? point2에서 설명하도록 하겠다.

 

 

 

 

Point 2) if문의 비교 시에 범주를 잘 확인하자

 

if high_y<=arr[i][1]:

 

마지막 네 번째 코드블럭에서 if문에서 <=와 같이 처리하지 않고 <로 처리 시에는 위의 문제예제와 (1) case와 (2) case는 모두 해결할 수 있다. 하지만 (3) case는 해결할 수 없다.

 

(3) case를 해결하기 위해서는 high_y와 같은 경우도 처리를 하면 공통 최댓값을 처리할 수 있다. <과 <=차이로 반례케이스를 해결할 수 있는 경우인 것이다.