백준 / 실버 V / 2628. 종이 자르기

• 가로와 세로가 굉장히 헷갈리는 문제

• 가로로 자를 땐 세로 변 기준으로 종이가 나뉘고, 세로로 자를 땐 가로 변 기준으로 종이가 나뉨
  • 예를 들어 세로 길이가 8인데, 가로에서 3 지점을 자르면, 세로 변 기준으로 (0, 3), (3, 8) 2개로 종이가 잘림
  • 당연한 소리 같지만, 막상 문제 풀어보면 가로, 세로가 헷갈림

나의 풀이

A, B = map(int, input().split()) # A: 가로의 길이, B: 세로의 길이
T = int(input())

a_cuts = [0, A]		# 세로로 자른 지점들 (즉 가로 변에서 잘린 지점들)
b_cuts = [0, B]		# 가로로 자른 지점들 (즉 세로 변에서 잘린 지점들)

for _ in range(T):
    how, loc = map(int, input().split())
    if how == 0:    # 가로 자르기
        b_cuts.append(loc)
    elif how == 1:  # 세로 자르기
        a_cuts.append(loc)
        
a_cuts.sort()
b_cuts.sort()

a_lens = []
b_lens = []    

for i in range(1, len(a_cuts)):
    a_lens.append(a_cuts[i] - a_cuts[i-1])

for i in range(1, len(b_cuts)):
    b_lens.append(b_cuts[i] - b_cuts[i-1])

result = max(a_lens) * max(b_lens)
print(result)

• 가로 변 및 세로 변에서 잘린 각 부분의 길이를 계산 후, 제일 긴 부분끼리 곱하면 됨
• a_cuts엔 세로로 자른 지점들 (즉 가로 변에서 잘린 지점들)을 저장
  • 이때 양끝 (0, 가로 길이)도 함께 포함
• b_cuts엔 가로로 자른 지점들 (즉 세로 변에서 잘린 지점들)을 저장
  • 이때 양끝 (0, 세로 길이)도 함께 포함
• a_cuts, b_cuts을 정렬한 뒤, 잘린 부분별 길이를 계산해 a_lens, b_lens에 저장한다.
• a_lens, b_lens 중 최댓값을 서로 곱하면 정답

시간 복잡도

• 자른 지점의 수를 $N$으로 둘 때,
  • 자른 지점을 순회하며 $O(N)$
  • a_cuts, b_cuts 정렬하며 $O(N \log N)$
  • 각 부분의 길이를 계산하며 $O(N)$
  • 최댓값을 계산하며 $O(N)$
• 최종 $O(N \log N)$

기억할 점

• 문제에 '가로', '세로', '행', '열', '격자' 등 표현이 보이는 순간, 즉시 종이에 그림부터 그리자. 머릿속에 떠올리며 풀려고 시도하다간 도중에 100% 헤맨다.