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

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

2304번: 창고 다각형

 

bucket이라는 새로운 배열을 만들고, 

검은 선에 해당하는 부분을 숫자로 채우는 식으로 발상을 했다.

즉, 새로운 bucket은 [0, 0, 4, 4, 6, 6, 6, 6, 10, 8, 8, 8, 8, 8, 8, 8, 0, 0, ...]

그리고 bucket안에있는 수를 총합하면 다각형의 면적이 된다.

 

일단 주어진 input을 모두 bucket에 담아서 위 사진같은 bucket을 만든다

N = int(input())
arr = [list(map(int, input().split())) for _ in range(N)]
bucket = [0]*1001

for i in range(len(arr)):
    bucket[arr[i][0]] = arr[i][1]

#지붕에서 제일 높은 지점
rooftop = max(bucket)

그리고, 지붕에서 제일 높은 지점을 기준으로 양 옆을 다르게 생각할 것이기 때문에

rooftop변수에 제일 높은 지점을 저장한다.

rooftop_idx = 0
for i in range(len(bucket)):
    if bucket[i]==rooftop:
        rooftop_idx = i

그리고 지붕에서 제일 높은 지점을 가지는 index를 찾는다.

이 index 기준으로 넓이를 계산할것

 

 

#처음부터 제일 높은 지점까지는 증가하면서 fill
for i in range(1, rooftop_idx):
    if bucket[i-1]>=bucket[i]:
        # 전 칸보다 지금 칸의 높이가 작으면
        # 전칸 높이로 대체하기
        bucket[i] = bucket[i-1]

#제일 높은 지점부터 끝까지는 거꾸로 가면서 fill
for i in range(len(bucket)-2, rooftop_idx, -1):
    # 왼쪽 칸의 높이가 지금 칸 높이 보다 크면
    # 왼쪽 칸 높이로 대체
    if bucket[i+1] >= bucket[i]:
        bucket[i] = bucket[i+1]

이렇게 bucket에 다각형 넓이를 저장했으면, 

for문을 한번 돌면서 넓이를 total에 추가해주면 된다.

total = 0
for i in range(len(bucket)):
    total += bucket[i]

print(total)

 

 

전체 풀이)

N = int(input())
arr = [list(map(int, input().split())) for _ in range(N)]

bucket = [0]*1001

for i in range(len(arr)):
    bucket[arr[i][0]] = arr[i][1]

#지붕에서 제일 높은 지점
rooftop = max(bucket)
rooftop_idx = 0
for i in range(len(bucket)):
    if bucket[i]==rooftop:
        rooftop_idx = i

#처음부터 제일 높은 지점까지는 증가하면서 fill
for i in range(1, rooftop_idx):
    if bucket[i-1]>=bucket[i]:
        # 전 칸보다 지금 칸의 높이가 작으면
        # 전칸 높이로 대체하기
        bucket[i] = bucket[i-1]

#제일 높은 지점부터 끝까지는 거꾸로 가면서 fill
for i in range(len(bucket)-2, rooftop_idx, -1):
    # 왼쪽 칸의 높이가 지금 칸 높이 보다 크면
    # 왼쪽 칸 높이로 대체
    if bucket[i+1] >= bucket[i]:
        bucket[i] = bucket[i+1]

total = 0
for i in range(len(bucket)):
    total += bucket[i]

print(total)