[Python/백준] 2628. 종이자르기

문제 접근 및 공부 내용, 풀이는 모두 하단 코드에 "주석"으로 포함되어 있으니 참고해주세요.

문제 유형 보기

이차원 리스트 + 구현

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

---

현장에서 모의고사로 푼 풀이

import sys
input = sys.stdin.readline

# 간선을 좌표로 가지면, 될거같은데?
# n x m = 8 x 10이라 하면,
# 이걸 9 x 11로 만들어서, 간선을 자를 수 있을듯.

# n = n + 1
# m = m + 1
# # ex. 10 8 들어오면 -> 9 x 11이다.
# paper = [[True] * m for _ in range(n)]
#
# iter_of_cutting = int(input())
# for _ in range(iter_of_cutting):
#     operand, line_number = map(int, input().split())
#
#     if operand == 0:
#         # 가로로 자를 거임
#         for j in range(m):
#             paper[line_number][j] = False
#
#     else:
#         # 세로로 자를 거임
#         for i in range(n):
#             paper[i][line_number] = False
#
# answer = 0
# print(answer)


m, n = map(int, input().split())

# 아
# 이거 그냥 가로 후보들, 세로 후보들 다 늘여놓고,
# 거기서 경우의 수 n + 1 x m + 1 다 센다음
# 그 중에 max 구하면 되겠는데?

iter_of_cutting = int(input())

cuttings_garo = [0, n]
cuttings_sero = [0, m]


for _ in range(iter_of_cutting):
    operand, line_number = map(int, input().split())

    if operand == 0:
        # 가로로 자를 거임
        cuttings_garo.append(line_number)

    else:
        # 세로로 자를 거임
        cuttings_sero.append(line_number)

cuttings_garo.sort()
cuttings_sero.sort()
# print(cuttings_garo)
# print(cuttings_sero)
# [0, 2, 3, 8]
# [0, 4, 10]

seros = []
garos = []

for i in range(len(cuttings_garo) - 1):
    seros.append(cuttings_garo[i+1] - cuttings_garo[i])


for i in range(len(cuttings_sero) - 1):
    garos.append(cuttings_sero[i+1] - cuttings_sero[i])

# print(seros)
# print(garos)

max_area = 0
for sero in seros:
    for garo in garos:
        max_area = max(max_area, garo*sero)

print(max_area)

이런 문제를 ‘시뮬레이션’ 문제라 함.

삼성에서 이 유형을 참 좋아하고, 이런 걸 보는 기업들이 많이지고 있음.

고급 알고리즘 필요 없이, 언어 자체의 내장 함수 및 메서드들로, 순수 사고력으로 풀어야하는 문제.

---

집와서 다시 풀어본 풀이