Mingssssss

1. 문제

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

<그림 1>

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

<그림 2>

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

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

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

2. 코드

import sys
sys.stdin = open('input.txt')


def slicing_paper():

    row_list = []
    column_list = []
    paper_list = []

    for rc in arr:   # arr에 받아온 row/column 리스트를 각각의 리스트에 저장
        if rc[0] == 0:
            column_list.append(rc[1])
        else:
            row_list.append((rc[1]))
    row_list.sort()   # 오름차순으로 정렬
    column_list.sort()

    if not column_list:   # column_list가 비어있을 때의 조건
        for r in range(len(row_list)+1):  # column이 없으므로 row값만 확인해서 M(가로)값과 곱해서 확인
            if r == 0:
                paper_list.append(row_list[0] * M)
            elif r == len(row_list):
                paper_list.append((N - row_list[-1]) * M)
            else:
                paper_list.append((row_list[r]-row_list[r-1]) * M)
    elif not row_list:  # row_list가 비어있을 때의 조건
        for c in range(len(column_list) + 1):  # row가 없으므로 column값만 확인해서 N(세로)값과 곱해서 확인
            if c == 0:
                paper_list.append(column_list[0] * N)
            elif c == len(column_list):
                paper_list.append((M - column_list[-1]) * N)
            else:
                paper_list.append((column_list[c] - column_list[c - 1]) * N)
    else:  # row/column이 빈 리스트가 아닐 때의 조건
        for i in range(len(column_list)+1):
                for j in range(len(row_list)+1):
                    if j == 0 and i == 0:  # 맨 첫 번째의 조건. 리스트의 맨 첫번째의 값을 곱한다.
                        paper_list.append(column_list[i] * row_list[j])
                    elif j == len(row_list):  # row 값이 마지막일 때,
                        if i == 0 and len(row_list) == 1:  # column 값이 첫 번째 값이고, row 값이 하나밖에 없다면,
                            paper_list.append(column_list[0] * (N - row_list[0]))  # column 첫 번째 값과 N-row 값을 곱함.
                        elif i == len(column_list):  # column 값이 마지막일 경우,
                            paper_list.append((M - column_list[-1]) * (N - row_list[-1]))  # row 값도 마지막이므로 해당 값을 곱함.
                        elif i == 0:  # column 값이 첫 번째일 경우,
                            paper_list.append((column_list[0] * (N - row_list[-1])))  # column은 첫 번째 값, row 값은 해당 값을 곱함.
                        else:  # 그 밖의 경우, column은 처음과 끝이 아닌 가운데 값이므로 해당 값을, row는 N-row 값을 곱함.
                            paper_list.append((column_list[i]-column_list[i-1]) * (N - row_list[-1]))
                    elif i == len(column_list):
                        if len(column_list) == 1:
                            paper_list.append((N - column_list[-1]) * row_list[j])
                        elif j == len(row_list):
                            paper_list.append((N - column_list[-1]) * (M - row_list[-1]))
                        elif j == 0:
                            paper_list.append((M - column_list[-1]) * (row_list[0]))
                        else:
                            paper_list.append((M - column_list[-1]) * (row_list[j]-row_list[j-1]))
                    else:
                        if len(row_list) == 1:
                            paper_list.append((column_list[i] - column_list[i - 1]) * row_list[0])
                        elif len(column_list) == 1:
                            paper_list.append(column_list[0] * (row_list[j] - row_list[j - 1]))
                        elif i == 0:
                            paper_list.append(column_list[0] * (row_list[j]-row_list[j-1]))
                        elif j == 0:
                            paper_list.append((column_list[i]-column_list[i-1]) * (row_list[0]))
                        else:
                            paper_list.append((column_list[i]-column_list[i-1]) * (row_list[j]-row_list[j-1]))

    return print(max(paper_list))



N, M = map(int, (input().split()))
cutting_num = int(input())
arr = [list(map(int, input().split())) for _ in range(cutting_num)]

slicing_paper()

3. 리뷰

초초하드코딩으로 작성했다. 나중에 꼭 다른 방법으로 다시 풀고 싶은 문제이다.
최대한 간단하게 생각하려고 노력했다.
사각형의 넓이의 합은 가로x세로이므로, 색종이를 자르고 나서의 조각의
가로와 세로의 길이를 곱해서 그 중에 가장 큰 값을 return 하려고 했다.
그렇게 하기 위해선 가로와 세로로 잘랐을 때 몇 조각이 나오는지 확인해야 했다.
row=[a1, a2, a3, ... an]
column=[b1, b2, b3, ... bn]
N , M = 가로, 세로
이라고 했을 때, 각각의 가로와 세로의 길이는
a1, (a2-a1), (a3-a2) ... (N-an)
b1, (b2-b2), (b3-b2) ... (M-bn) 의 공식이 나왔다.
공식을 그대로 코드로 구현하려고 하니 경우의 수가 너무 많이 생겼다.
row와 column이 3개 이상 값이 들어오면 문제가 없으나,
각각 값이 1개 혹은 2개만 있다면 (a2-a1)의 값도 구현이 안 되고,
값이 하나만 있다면, 그 값을 고정 시켜야 하고,
row와 column이 비어있을 때의 조건도 생각해야 했다.
하나 하나 하드코딩하다가 중간에 포기도 하고 싶었지만 오기가 생겼다.
예상되는 경우의 수를 하나씩 체크해가며 디버깅으로 코드를 추가했다.
정말 마지막의 마지막까지 체크를 한 뒤 제출해도 틀렸다고 나왔다.
밤에 자기 전까지 어디서 예외가 나왔나 고민하다가 잔 문제인 것 같다.
마지막으로 처음부터 하나하나 조건을 확인하고 제출하니 정답이였다.
하드코딩도 좋지만, 더 간단히 생각하고 구현하려는 노력을 해야겠다.