[BOJ #2628] 종이자르기

문제

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

<그림 1>

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

<그림 2>

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

 

입력

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

 

출력

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

 

내가 쓴 코드 1

# 하드코딩 ver.
from sys import stdin ; input = stdin.readline
# N : 가로, M : 세로
N, M = map(int, input().split())
row = [i for i in range(N+1)]   # 나눠진 가로 길이들 0~7 중 1~7 사용
col = [i for i in range(M+1)]   # 나눠진 세로 길이들 0~9 중 1~9 사용
# cut_num : 자를 점선 개수
cut_num = int(input())
r = []
c = []
for _ in range(cut_num):
    # cut = 0 : 가로, cut = 1 : 세로, line : 자르는 점선 번호
    cut, line = map(int, input().split())
    # 가로 선 자르기
    if cut == 0:
        c.append(line)
    # 세로 선 자르기
    if cut == 1:
        r.append(line)
# 오름차순 정렬
r.sort()
c.sort()
r_len = []
c_len = []
r_cnt = c_cnt = 0
def cut_func(l):
    global r_cnt, c_cnt
    if c:   # 가로 자르기
        a = c.pop(0)
        c_len.append(col[l+1:a+1])
        c_cnt += 1
        cut_func(a)
        c_len.append(col[a+1:])
    if r:   # 세로 자르기
        a = r.pop(0)
        r_len.append(row[l+1:a+1])
        r_cnt += 1
        cut_func(a)
        r_len.append(row[a+1:])
    return c_len, r_len

cut_func(0)
# 가로 길이 리스트
for _ in range(c_cnt-1):
    c_len.pop()
# 세로 길이 리스트
for _ in range(r_cnt-1):
    r_len.pop()

max_area = area = 0
for rl in r_len:
    for cl in c_len:
        area = len(rl) * len(cl)
    if area > max_area:
        max_area = area
print(max_area)

움.. 머가 틀린지 모르겠다. 일단 런타임 에러가 날 것 같긴 했다. 리스트를 워낙 많이 만들고, 코드가 너무 길어서.... 그래두 속상.. 그래서 다른 풀이 보고 코드 다 갈아엎었다! 아래 코드가 갈아 엎은 코드!!!

 

내가 쓴 코드 2

# 절약 ver.
from sys import stdin ; input = stdin.readline
# N : 가로, M : 세로
N, M = map(int, input().split())
row = [0, N]    # 행 -> 세로 자르는 점선 번호
col = [0, M]    # 열 -> 가로 자르는 점선 번호
# cut_num : 자를 점선 개수
cut_num = int(input())
for _ in range(cut_num):
    # cut = 0 : 가로, cut = 1 : 세로, line : 자르는 점선 번호
    cut, line = map(int, input().split())
    # 가로 선 자르기
    if cut == 0:
        col.append(line)
    # 세로 선 자르기
    if cut == 1:
        row.append(line)
# 오름차순 정렬
row.sort()
col.sort()
max_area = 0
for i in range(len(row) - 1):
    for j in range(len(col) - 1):
        width = row[i+1] - row[i]
        height = col[j+1] - col[j]
        max_area = max(max_area, width*height)
print(max_area)

간단하게 고치고나서 보니, 내가 썼던 코드는 너무 어렵게 풀어갔다는 생각이 든다. 그냥 길이를 구해서 넓이 최대 구하는 것까지 한 번에 처리할 수 있는데, 나는 그것들을 다 따로 처리했다.. 합쳐서 구현하는 연습을 더 해야겠다...

나중에 내 코드를 봤을 때 나도 이해 못할 것 같긴 하다..^^* ㅎㅋ,,

 

제출 결과

 

맞았습니다 코드가 2번째 코드, 나머진 1번째 코드.. 미련을 버리지 못했지만,, 실패 !! ㅋㅋㅋㅋ