0302. [BOJ#2628] 종이 자르기

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

2628번: 종이자르기

1 초

128 MB

10775

5866

4874

55.305%

문제

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

 

<그림 1>

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

 

<그림 2>

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

입력

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

출력

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

---

제출 코드

row = [0] 
col = [0] 
r, c = map(int, input().split())
row.append(r)
col.append(c)
# 잘라야 하는 점선의 개수
M = int(input())

# M번 자르기
for i in range(M):
    # case: 0 > 가로줄자르는선(col이랑 비교) , case: 1 > 세로줄자르는선(row이랑 비교)
    case, num = map(int, input().split())
    if case == 0:
        col.append(num)
    if case == 1:
        row.append(num)
        
row.sort() # 오름차순정렬
col.sort()

ans_row = 0
for k in range(len(row)):
    if 0 <= k+1 < len(row):
        row_max_val = row[k+1] - row[k]
        if ans_row <= row_max_val:
            ans_row = row_max_val

ans_col = 0
for j in range(len(col)):
    if 0 <= j+1 < len(col):
        col_max_val = col[j+1] - col[j]
        if ans_col <= col_max_val:
            ans_col = col_max_val

result = ans_row * ans_col
print(result)

평소에 배열에 값이 들어가 있는 문제만 풀다가 다른 유형의 문제를 보니 어떻게 해야할지 전혀 감이 잡히지 않았다.

고민을 오래했는데 구현이 힘들어서 미량,소정누나의 코드를 봤는데 그래도 모르겠어서 강의를 찾아봤다.

youtube - 문어박사 IT편의점

영상 초반의 이 그림을 보고나니까 생각이 번뜩이면서 금방 구현을 했다.

그럼에도 불구하고 틀린건 첫 가로 세로 리스트값에 0을 넣어주지 않아서 + 디버깅용 print 를 넣고 돌려서 틀렸는데 다행히 금방 찾아내서 제출할 수 있었다. 기본기의 중요성을 깨닫게 해준문제.

배열 구현은 언제쯤 익숙해질까..