[BOJ]2304. 倉庫ポリゴン

❌code1

def warehouse(w_list):
    w_list.sort()    # 받은 리스트를 좌표순으로 정렬
    max_height = 0    # 건물 최대 높이

    for w in w_list:
        if w[1] > max_height:
            max_height = w[1]    # 기둥의 최대 높이
      
    # 최대 높이를 기준으로 면적 설정
    area = max_height

    # 가장 높은 기둥 왼쪽의 면적 구하기
    local_max = w_list[0][1]
    local_m_i = w_list[0][0]
    i = 0
    while True:
        if w_list[i][1] == max_height:  # 높이가 같은 경우
            area += (w_list[i][0] - local_m_i) * local_max
            break
        elif w_list[i][1] > local_max:  # 더 높은 기둥을 만난 경우
            area += (w_list[i][0] - local_m_i) * local_max
            local_max = w_list[i][1]
            local_m_i = w_list[i][0]
        i += 1
    
    # 가장 높은 기둥 오른쪽의 면적 구하기
    i = 0
    local_max = w_list[-1][1]
    local_m_i = w_list[-1][0]
    while True:
        if w_list[-1-i][1] == max_height:  # 높이가 같은 경우
            area += (local_m_i - w_list[-1-i][0]) * local_max
            break

        elif w_list[-1-i][1] > local_max:  # 더 높은 기둥을 만난 경우
            area += (local_m_i - w_list[-1-i][0]) * local_max
            local_max = w_list[-1-i][1]
            local_m_i = w_list[-1-i][0]
        i += 1

    return area

    
N = int(input())

my_w_list = []
for i in range(N):
    my_w_list.append(list(map(int, input().split())))

print(warehouse(my_w_list))

試す

質問する

⭕code2

def warehouse(col_list):
    # 기둥 높이를 반영한 창고 바닥 리스트를 만든 이후
    # 내림차순으로 정렬된 기둥 높이를 돌면서 
    # 현재 기둥 위치와 다음 기둥 위치 사이의 높이를 두 기둥 중 낮은 기둥 높이로 채움

    # 기둥 높이를 기준으로 내림차순 정렬된 리스트 생성
    check_list = sorted(col_list, key=lambda x: x[1], reverse=True)

    col_list.sort()    # 기둥 리스트를 위치순으로 정렬
    c_list = []    # 기둥의 높이만을 담은 리스트 생성, 창고 바닥을 나타냄
 
    while True:    # 창고 바닥의 높이를 기록, 기둥이 없으면 0, 기둥이 있으면 해당 높이
        if len(col_list) == 0:    # 기존 리스트에서 기둥이 모두 사라지면 break
            break
        elif col_list[0][0] == len(c_list):
            c_list.append(col_list[0][1])    # 기둥이 있으면 그 높이를 넣음
            col_list = col_list[1:]    # 기존의 리스트에서 제거
        else:    
            c_list.append(0)    # 기둥이 없으면 0
  
    for i in range(len(check_list)-1):
        # 현재 기둥 위치와 다음 기둥 위치를 정하는 두 개의 변수
        x1 = min(check_list[i][0], check_list[i+1][0])
        x2 = max(check_list[i][0], check_list[i+1][0])

        # 기둥 사이의 위치들을 돌며 그 높이가 낮은 기둥 높이보다 낮다면 새로 갱신
        for j in range(x1, x2+1):
            if c_list[j] < check_list[i+1][1]:
                c_list[j] = check_list[i+1][1]

    result = sum(c_list)    # 창고 바닥에 적힌 숫자를 모두 더하면 최종 결과

    return result
    

N = int(input())

my_col_list = []
for i in range(N):
    my_col_list.append(list(map(int, input().split())))

print(warehouse(my_col_list))

試す

質問する

⭕code3

import sys


def warehouse(start, end, direction):
    curr_column = ()  # 현재 최고 높이 기둥 정보
    area = 0  # 창고 면적
    for idx in range(start, end, direction):
        # 최고 높이 기둥을 넘어서면 중지
        if columns[idx][0] * direction > max_l * direction:
            return area

        if not curr_column:  # 저장된 기둥 정보가 없는 경우 초기 정보 저장
            curr_column = columns[idx]

        # 더 높은 기둥을 만난 경우 면적과 현재 최고 높이 기둥 갱신
        elif curr_column[1] <= columns[idx][1]:  
            area += (columns[idx][0] - curr_column[0]) * curr_column[1] * direction
            curr_column = columns[idx]
    return area


N = int(sys.stdin.readline())

# 기둥의 왼쪽 면의 위치, 높이를 튜플로 리스트에 저장
columns = [tuple(map(int, sys.stdin.readline().split())) for _ in range(N)]
columns.sort()  # 왼쪽 면의 위치를 기준으로 정렬

# 최고 높이 기둥의 위치를 구해 이를 기준으로 좌측, 우측 창고를 따로 계산
max_l, max_height = max(columns, key=lambda x: x[1])

ans = warehouse(0, N, 1)  # 최고 높이 기둥의 좌축
ans += warehouse(N - 1, -1, -1)  # 최고 높이 기둥의 우측

print(ans + max_height)

試す

サマリ