BOJ(백준) 2304[창고 다각형]

안녕하세요! 오늘은 백준 온라인 저지의 문제 번호 2304번을 풀어보겠습니다. 이 문제는 주어진 기둥들의 위치와 높이를 이용하여 창고 다각형의 면적을 구하는 문제입니다.

 

문제 URL: https://www.acmicpc.net/problem/2304

 

1. 문제 설명

주어진 기둥들의 위치와 높이를 이용하여 창고 다각형의 면적을 구하는 문제입니다. 기둥의 위치와 높이를 고려하여 전체 다각형의 면적을 계산합니다.

 

2. 접근법

1. 기둥의 개수를 입력받습니다.

2. 각 기둥의 위치와 높이를 입력받아 리스트에 저장합니다.

3. 가장 높은 기둥의 위치와 높이를 찾습니다.

4. 왼쪽에서 오른쪽으로 이동하며 면적을 계산합니다.

5. 오른쪽에서 왼쪽으로 이동하며 면적을 계산합니다.

6. 두 부분의 면적을 합산하여 최종 면적을 출력합니다.

 

3. 정답 코드

import sys
input = sys.stdin.readline

# 기둥의 개수 입력처리
N = int(input())

# 기둥의 높이를 저장할 리스트 초기화 (최대 1000까지의 위치)
phi = [0] * 1001
maxL = 0  # 가장 높은 기둥의 위치
maxH = 0  # 가장 높은 기둥의 높이

# 기둥 입력
for _ in range(N):
    L, H = map(int, input().split())
    if H > maxH:
        maxH = H
        maxL = L
    phi[L] = H

curH = 0  # 현재 높이
ans = 0   # 면적 합

# 왼쪽에서 가장 높은 기둥까지 면적 계산
for i in range(maxL + 1):
    if phi[i] > curH:
        curH = phi[i]
    ans += curH

curH = 0  # 현재 높이 초기화

# 오른쪽에서 가장 높은 기둥까지 면적 계산
for i in range(1000, maxL, -1):
    if phi[i] > curH:
        curH = phi[i]
    ans += curH

# 최종 면적 출력
print(ans)

 

4. 코드 설명

1. 기둥의 개수 입력 처리

• N을 입력받습니다.

2. 기둥 입력

• 각 기둥의 위치 L과 높이 H를 입력받아 리스트 phi에 저장합니다.

• 가장 높은 기둥의 위치 maxL과 높이 maxH를 업데이트합니다.

3. 왼쪽에서 가장 높은 기둥까지 면적 계산

• 현재 높이 curH를 업데이트하면서 왼쪽에서 오른쪽으로 이동하며 면적을 계산합니다.

• 기둥이 더 높은 경우, 현재 높이를 업데이트하고 면적에 더합니다.

4. 오른쪽에서 가장 높은 기둥까지 면적 계산

• 현재 높이 curH를 초기화합니다.

• 오른쪽에서 왼쪽으로 이동하며 면적을 계산합니다.

• 기둥이 더 높은 경우, 현재 높이를 업데이트하고 면적에 더합니다.

5. 최종 면적 출력

• 계산된 면적 ans를 출력합니다.

5. Github으로 확인

coTest/BOJ/BOJ01_03_03_2304.py at main · pcy4196/coTest