[백준/Python] 16937 두 스티커

 

📌 문제 탐색하기

• 크기 HxW 모눈종이, 스티커 N개
  • 모눈종이 크기는 1x1인 칸으로 나누어지고, 간격 1을 두고 선이 그어져 있음
  • i번째 스티커의 크기 : R(i)xC(i)
• 모눈종이에 스티커 2개를 붙이고자 함
  • 스티커의 변이 격자의 선과 일치하도록
  • 두 개의 스티커가 서로 겹치지 않도록 (인접하는 것은 가능)
  • 스티커를 90도 회전 가능
  • 스티커가 모눈종이를 벗어나는 것은 불가능
• 두 스티커가 붙여진 넓이의 최댓값 구하기 (두 스티커를 붙일 수 없는 경우 0 출력)

 

모눈종이의 높이와 너비인 H, W와 스티커의 개수 N이 각각 최대 100을 넘지 않아 주어진 수의 크기가 작으므로, 모든 경우의 수를 탐색하는 브루트포스 알고리즘을 고려해볼 수 있다. 

N개의 스티커들 중 2가지의 스티커를 골라서 ①둘 다 회전시키지 않는 경우 ②첫번째 스티커만 회전시키는 경우 ③두번째 스티커만 회전시키는 경우 ④둘 다 회전시키는 경우 이렇게 네가지의 경우를 모두 고려해서 스티커를 붙일 수 있는지 확인해서 현재 스티커들의 넓이를 구한다. 모든 경우에 대해 시도해본 후 두 스티커가 붙여진 넓이의 최댓값을 구한다.

 

 

---

📌 코드 설계하기

1. 모눈 종이의 크기 H, W와 스티커의 수 N을 입력받는다.
2. N개의 스티커 크기를 stickers 리스트로 입력받는다.
3. 붙인 스티커의 최댓값을 저장할 변수 max_area를 0으로 초기화한다.
4. stickers에서 스티커를 두 개씩 선택한 후 아래 경우를 모두 탐색하며 최대 스티커 넓이 max_area를 갱신한다. 이때, 모눈종이에 스티커를 붙일 수 있는 지 여부는 ①두 스티커를 세로로 이어 붙인 경우 ②두 스티커를 가로로 이어 붙인 경우를 모두 체크한다.
   1. 스티커를 모두 회전시키지 않은 상태
   2. 첫번째 스티커만 회전시킨 상태
   3. 두번째 스티커만 회전시킨 상태
   4. 스티커를 모두 회전시킨 상태
5. 모든 경우에 대한 탐색이 끝나면, max_area를 출력한다.

 

---

📌 정답 코드

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

stickers = [tuple(map(int, input().split())) for _ in range(N)]

max_area = 0

for i in range(N):
    for j in range(1, N):
        if i == j:
            continue
        
        w1, h1 = stickers[i]
        w2, h2 = stickers[j]
        current_area = w1 * h1 + w2 * h2
        
        if max_area >= current_area:
            continue
        
        # 1. 스티커를 모두 회전시키지 않은 상태
        if (h1 + h2 <= H and max(w1, w2) <= W) or (w1 + w2 <= W and max(h1, h2) <= H):
            max_area = current_area
            continue
        
        # 2. 1번 스티커만 회전시킨 상태
        if (w1 + h2 <= H and max(h1, w2) <= W) or (h1 + w2 <= W and max(w1, h2) <= H):
            max_area = current_area
            continue
            
        # 3. 2번 스티커만 회전시킨 상태
        if (h1 + w2 <= H and max(w1, h2) <= W) or (w1 + h2 <= W and max(h1, w2) <= H):
            max_area = current_area
            continue
            
        # 4. 두 스티커 모두 회전시킨 상태
        if (w1 + w2 <= H and max(h1, h2) <= W) or (h1 + h2 <= W and max(w1, w2) <= H):
            max_area = current_area
            continue

print(max_area)