[알고리즘] 백준 파이썬 16937 두 스티커

 

📍 문제 탐색하기

크기가 H × W인 모눈종이와 N개의 스티커가 있다.
각 스티커는 Ri × Ci 크기이며, 스티커 2개를 겹치지 않게 붙이려고 한다.
스티커는 90도 회전이 가능하며, 종이를 벗어나서는 안 된다.
두 스티커가 차지하는 넓이의 최댓값을 구해야 한다.

---

📋 문제 조건

• 1 ≤ H, W, N ≤ 100
• 1 ≤ Ri, Ci ≤ 100
• 스티커의 변은 모눈종이의 선과 일치해야 한다.
• 스티커끼리 겹치는 것은 불가능하지만, 접하는 것은 가능하다.
• 두 스티커를 붙일 수 없으면 0을 출력한다.

---

⏱️ 시간 복잡도 고려

• 브루트포스 접근:
  두 개의 스티커를 선택하고, 각각을 회전시키는 모든 경우를 탐색해야 한다.
• 최대 경우의 수:
  • 스티커 선택: 약 5,000쌍 (100C2)
  • 각 스티커당 2가지 회전 → 총 4가지 경우
  • 최대 20,000번 탐색 → 시간 제한 2초 내 충분히 가능하다.

---

📍 코드 설계하기

1. 스티커 두 개를 선택한다.
2. 각 스티커를 회전(90도) 한 경우도 고려한다.
3. 스티커를 가로로 나란히, 또는 세로로 나란히 붙일 수 있는지 확인한다.
4. 조건을 만족하면 넓이의 합을 구하고, 최대값을 갱신한다.

---

📍 시도 회차 및 수정 사항

import sys
input = sys.stdin.readline

H, W = map(int, input().split())
N = int(input())

lst = []
result = []

for _ in range(N):
    R, C = map(int, input().split())
    lst.append([R,C])
    
max_area = 0

for i in range(len(lst)-1):
    for j in range(i+1, len(lst)):
        (r1, c1) = lst[i]
        (r2, c2) = lst[j]
        
        for (nr1, nc1) in [(r1, c1), (c1, r1)]:
            for (nr2, nc2) in [(r2, c2), (c2, r2)]:
                if (nr1 + nr2 <= H) and (max(nc1, nc2) <= W):
                    max_area = max(max_area, nr1 * nc1 + nr2 * nc2)

                if (max(nr1, nr2) <= H) and (nc1 + nc2 <= W):
                    max_area = max(max_area, nr1 * nc1 + nr2 * nc2)
                    
print(max_area)