본문 바로가기

백준 write-up/정렬 & 그리디

[백준] 종이자르기 : 2628번 - Python

728x90
반응형

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

 

2628번: 종이자르기

아래 <그림 1>과 같이 직사각형 모양의 종이가 있다. 이 종이는 가로방향과 세로 방향으로 1㎝마다 점선이 그어져 있다. 가로 점선은 위에서 아래로 1번부터 차례로 번호가 붙어 있고, 세로 점선

www.acmicpc.net

 

 

 

문제의 접근 방법

 

가로 점선을 잘랐을 때는 그 값을 세로길이에 저장하고, 세로 점선을 잘랐을 때는 그 값을 가로길이에 저장해야 한다.

(ex) 3번 가로점선을 따라 자를 경우 그 잘린 값이 세로의 길이가 된다.

 

 

 

내가 막혔던 부분

 

- 문제의 접근 방법

 

 

 

문제 풀이 방법

 

(1) 가로와 세로 길이 w,h 입력받기

(2) 자를 횟수 n번 입력받기

(3) 나중에 길이를 직사각형의 길이를 계산하기 위해 width, height 배열 선언 (여기서 0은 나중에 길이 계산을 위해 시작 인덱스를 표시해 준 것)

(4) 자르는 횟수 n번만큼 반복문을 돌린 후 a (가로로 자를 것인지, 세로로 자를 것인지)와 b (몇 번 줄을 자를 것인지)를 입력받기

(5) 조건문을 통해 a가 0이라면(가로) b값을 세로 배열(height)에 추가하고 1이라면(세로) b값을 가로배열(width)에 추가

(6) 배열 width,height를 정렬하기

(7) 정렬된 리스트들은 잘린 인덱스 번호를 넣어둔 것이기 때문에 두 원소의 차를 이용해 가로와 세로 길이들을 구하기

(8) 그 값들을 곱했을 때 가장 큰 값이 직사각형의 최대 넓이!

 

 

 

소스코드

w,h = map(int, input().split())
n = int(input())
width = [0, w]
height = [0, h]

for _ in range(n):
    a,b = map(int, input().split())
    if a == 0:
        height.append(b)
    elif a == 1:
        width.append(b)

width.sort()
height.sort()

result = 0

for i in range(len(width)-1):
    for j in range(len(height)-1):
        x = width[i+1] - width[i]
        y = height[j+1] - height[j]
        result = max(result, x*y)

print(result)
728x90
반응형