문제
아래 <그림 1>과 같이 직사각형 모양의 종이가 있다.
이 종이는 가로방향과 세로 방향으로 1㎝마다 점선이 그어져 있다.
가로 점선은 위에서 아래로 1번부터 차례로 번호가 붙어 있고, 세로 점선은 왼쪽에서 오른쪽으로 번호가 붙어 있다.
점선을 따라 이 종이를 칼로 자르려고 한다.
가로 점선을 따라 자르는 경우는 종이의 왼쪽 끝에서 오른쪽 끝까지, 세로 점선인 경우는 위쪽 끝에서 아래쪽 끝까지 한 번에 자른다.
예를 들어, <그림 1>의 가로 길이 10㎝이고 세로 길이 8㎝인 종이를 3번 가로 점선, 4번 세로 점선, 그리고 2번 가로 점선을 따라 자르면 <그림 2>와 같이 여러 개의 종이 조각으로 나뉘게 된다.
이때 가장 큰 종이 조각의 넓이는 30㎠이다.
입력으로 종이의 가로 세로 길이, 그리고 잘라야할 점선들이 주어질 때, 가장 큰 종이 조각의 넓이가 몇 ㎠인지를 구하는 프로그램을 작성하시오.
https://www.acmicpc.net/problem/2628
입력
첫줄에는 종이의 가로와 세로의 길이가 차례로 자연수로 주어진다.
가로와 세로의 길이는 최대 100㎝이다.
둘째 줄에는 칼로 잘라야하는 점선의 개수가 주어진다.
셋째 줄부터 마지막 줄까지 한 줄에 점선이 하나씩 아래와 같은 방법으로 입력된다.
가로로 자르는 점선은 0과 점선 번호가 차례로 주어지고, 세로로 자르는 점선은 1과 점선 번호가 주어진다.
입력되는 두 숫자 사이에는 빈 칸이 하나씩 있다.
출력
첫째 줄에 가장 큰 종이 조각의 넓이를 출력한다.
단, 넓이의 단위는 출력하지 않는다.
예제
# input
10 8
3
0 3
1 4
0 2
# output
30문제 풀이
# 가로, 세로 길이 입력 받기
w, h = map(int, input().split())
# 각각의 길이 시작과 끝을 리스트에 저장
width = [0, w]
height = [0, h]
# 자르는 횟수 입력 받기
N = int(input())
for _ in range(N):
w_h, length = map(int, input().split())
# w_h가 0이면 가로로 잘라 세로 길이에 영향
if w_h == 0:
height.append(length)
# w_h가 0이 아니면(1이면) 세로로 잘라 가로 길이에 영향
else:
width.append(length)
# 점선 위치 정렬
width.sort()
height.sort()
# 정답 변수 초기화
answer = 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]
# 가장 큰 넓이 업데이트
answer = max(answer, x*y)
print(answer)파이썬을 독학하시는 분들에게 도움이 되길 바라며,
혹 더 좋은 방법이 있거나 오류가 있다면 편하게 말씀 부탁드립니다.
