두 스티커 (백준 16937번)

문제

크기가 H×W인 모눈종이와 스티커 N개가 있다. i번째 스티커의 크기는 Ri×Ci이다. 모눈종이는 크기가 1×1인 칸으로 나누어져 있으며, 간격 1을 두고 선이 그어져 있다.

오늘은 모눈종이에 스티커 2개를 붙이려고 한다. 스티커의 변은 격자의 선과 일치하게 붙여야 하고, 두 스티커가 서로 겹치면 안 된다. 단, 스티커가 접하는 것은 가능하다. 스티커를 90도 회전시키는 것은 가능하다. 스티커가 모눈종이를 벗어나는 것은 불가능하다.

두 스티커가 붙여진 넓이의 최댓값을 구해보자.

입력

첫째 줄에 모눈종이의 크기 H, W, 둘째 줄에 스티커의 수 N이 주어진다. 다음 N개의 줄에는 스티커의 크기 Ri, Ci가 주어진다.

출력

첫째 줄에 두 스티커가 붙여진 넓이의 최댓값을 출력한다. 두 스티커를 붙일 수 없는 경우에는 0을 출력한다.

나의 풀이

import sys
from itertools import combinations
input=sys.stdin.readline

H,W=map(int,input().strip().split())
N=int(input().strip())
stickers=[]
for _ in range(N):
    stickers.append(list(map(int,input().strip().split())))
max_r=0
for s1,s2 in combinations(stickers,2):
    H1=H-s1[0]
    W1=W-s1[1]
    if H1>=0 and W1>=0:
        if (H1>=s2[0] and W>=s2[1]) or (H1>=s2[1] and W>=s2[0]) or (H>=s2[0] and W1>=s2[1]) or (H>=s2[1] and W1>=s2[0]):
            max_r=max(max_r,s1[0]*s1[1]+s2[0]*s2[1])
            continue
    H1=H-s1[1]
    W1=W-s1[0]
    if H1>=0 and W1>=0:
        if H1>=0 and W1>=0 and (H1>=s2[0] and W>=s2[1]) or (H1>=s2[1] and W>=s2[0]) or (H>=s2[0] and W1>=s2[1]) or (H>=s2[1] and W1>=s2[0]):
            max_r=max(max_r,s1[0]*s1[1]+s2[0]*s2[1])
print(max_r)
        

• 스티커를 가장자리에 붙일 때, 가장 효율적이다.
• 스티커 중 2개의 조합을 모두 구한 후, 첫번째 스티커를 붙였을 때 남는 공간에 대해, 그 다음 스티커를 붙일 수 있는지 확인하였다. (스티커는 회전 가능)
• 붙일 수 있는 경우의 수 중 가장 스티커의 넓이가 큰 값을 출력한다.