[백준] 2304 창고 다각형 python

문제

2304번: 창고 다각형

코드

N = int(input())

coordinate=[]

for i in range(N):
    coordinate.append(tuple(map(int,input().split())))

max_x = max(coord[0] for coord in coordinate)
max_y = max(coord[1] for coord in coordinate)

grid = [[0 for _ in range(max_x)] for _ in range(max_y)]

for x, y in coordinate:
    for i in range(y):
        grid[i][x - 1] = 1 

grid.reverse()

res=0

for i in range(len(grid)):
    if(grid[i].count(1)==0):
        continue
    if(grid[i].count(1)==1):
        res+=1
        continue
    front_index = grid[i].index(1) + 1
    back_index = len(grid[i]) - grid[i][::-1].index(1) 
    res+=back_index-front_index+1
print(res)

풀이

• 모든 기둥이 들어가는 최소 다각형 면적을 구해라

1. 좌표를 입력받아 기둥은 1, 빈공간은 0으로 이차원 배열을 만든다.
2. 배열을 y좌표 기준 한줄씩 돌면서 면적을 측정한다.
   1. 우선 한 줄에 기둥이 없으면 바로 다음줄로 넘어간다.
   2. 한 줄에 기둥이 한개 있으면 무조건 면적은 1이 추가된다.
   3. 한 줄에 기둥이 여러개 있으면 가장 바깥의 기둥 두개의 면적을 추가한다.