[백준 2628 🥈] 종이자르기

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

2628번: 종이자르기

문제

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

<그림 1>

점선을 따라 이 종이를 칼로 자르려고 한다. 가로 점선을 따라 자르는 경우는 종이의 왼쪽 끝에서 오른쪽 끝까지, 세로 점선인 경우는 위쪽 끝에서 아래쪽 끝까지 한 번에 자른다. 예를 들어, <그림 1>의 가로 길이 10㎝이고 세로 길이 8㎝인 종이를 3번 가로 점선, 4번 세로 점선, 그리고 2번 가로 점선을 따라 자르면 <그림 2>와 같이 여러 개의 종이 조각으로 나뉘게 된다. 이때 가장 큰 종이 조각의 넓이는 30㎠이다.

<그림 2>

입력으로 종이의 가로 세로 길이, 그리고 잘라야할 점선들이 주어질 때, 가장 큰 종이 조각의 넓이가 몇 ㎠인지를 구하는 프로그램을 작성하시오.

입력

첫줄에는 종이의 가로와 세로의 길이가 차례로 자연수로 주어진다. 가로와 세로의 길이는 최대 100㎝이다. 둘째 줄에는 칼로 잘라야하는 점선의 개수가 주어진다. 셋째 줄부터 마지막 줄까지 한 줄에 점선이 하나씩 아래와 같은 방법으로 입력된다. 가로로 자르는 점선은 0과 점선 번호가 차례로 주어지고, 세로로 자르는 점선은 1과 점선 번호가 주어진다. 입력되는 두 숫자 사이에는 빈 칸이 하나씩 있다.

출력

첫째 줄에 가장 큰 종이 조각의 넓이를 출력한다. 단, 넓이의 단위는 출력하지 않는다.

문제 풀이

• 가로 변을 자르는 선은 세로 선이므로, 첫 시작인 1번 선부터 for문 이용해서 탐색하면서 cur 변수에 +1해주다가 세로로 잘리는 선의 번호를 저장해둔 sero_cut의 값이 1인 번호를 만나면 가로 변의 가능한 길이를 저장해두는 garo_possible_line 배열에 cur 변수를 추가해주고, cur 변수를 1로 초기화한다.
• 이후 다시 for문을 돌면서 sero_cut의 값이 1인 번호를 만나면 또 cur 변수를 garo_possible_line에 추가해주는 식으로 해당 과정을 반복한다.
• 그러다 탐색하는 번호가 마지막 선 즉, (가로길이-1)번인 선을 만난다면, 해당 선이 잘리는 선이 아니라면 (sero_cut 값=0) 기존의 cur에 +1해서 추가해주고, 잘리는 선이라면(sero_cut 값=1) cur 그대로 추가해준다.
• 세로 변도 이와 같은 방식으로 세로 변의 가능한 길이를 sero_possible_line에 저장해둔다.
• 결과는 max(garo_possible_line)*max(sero_possible_line) 즉, 가능한 가장 긴 가로 길이와 세로 길이를 곱해준 값이 최대 넓이가 된다. 

import sys

garo, sero = map(int, sys.stdin.readline().split(' '))
num=int(sys.stdin.readline())

garo_cut=[0]*(sero)
sero_cut=[0]*(garo)
# how가 0이면 가로 줄, 1이면 세로 줄
for _ in range(num):
    how, line = map(int, sys.stdin.readline().split(' '))
    if how==0:
        garo_cut[line]=1
    elif how==1:
        sero_cut[line]=1

garo_possible_line=[]
sero_possible_line=[]
cur=1
for i in range(1,garo):
    if i==garo-1:
        if sero_cut[i]==1:
            garo_possible_line.append(cur)
        else:
            garo_possible_line.append(cur+1)
        break
    if sero_cut[i]==1:
        garo_possible_line.append(cur)
        cur=1
    else:
        cur+=1

cur=1
for i in range(1,sero):
    if i==sero-1:
        if garo_cut[i]==1:
            sero_possible_line.append(cur)
        else:
            sero_possible_line.append(cur+1)
        break
    if garo_cut[i]==1:
        sero_possible_line.append(cur)
        cur=1
    else:
        cur+=1

print(max(sero_possible_line)*max(garo_possible_line))

• 그런데 이 풀이는 풀면서도 더 간결하고 쉬운 풀이가 있을 것 같다는 생각을 했었지만, 쉽게 떠오르지 않아 풀이를 제출한 뒤에 통과를 받고 다른 분의 풀이를 확인했더니 훨씬 직관적인 풀이가 있었다..!

다른 사람 풀이

w,h = map(int,input().split())
W = [w,0]
H = [h,0]
T = int(input())

for i in range (0,T):
  d, n = map(int,input().split())
  if d == 0:
    H.append(n)
  if d == 1:
    W.append(n)

W.sort()
H.sort()

width=[]
for i in range (1,len(W)):
  for j in range (1,len(H)):
    width.append((W[i]-W[i-1]) * (H[j]-H[j-1]))

print(max(width))

위 그림과 같이 W 배열에 가로 변의 기준이 되는 점들을 모두 저장해두고, H 배열에 세로 변의 기준이 되는 점들을 모두 저장해준 뒤에

W[i]-W[i-1], H[i]-H[i-1] 과 같이 가능한 모든 변의 길이들을 서로 곱해준 뒤에 가장 큰 값을 구하는 것이다.

 

이런 풀이를 생각해낼 줄 아는 사람이 되자!