[백준/16937/파이썬] 두 스티커

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

16937번: 두 스티커

Problem

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

조건

• 스티커의 변은 격자의 선과 일치하게 붙여야 하고, 두 스티커가 서로 겹치면 안 된다. 단, 스티커가 접하는 것은 가능하다. 스티커를 90도 회전시키는 것은 가능하다. 스티커가 모눈종이를 벗어나는 것은 불가능하다.
• 두 스티커가 붙여진 넓이의 최댓값을 구해보자.
• 첫째 줄에 모눈종이의 크기 H, W, 둘째 줄에 스티커의 수 N이 주어진다. 다음 N개의 줄에는 스티커의 크기 Ri, Ci가 주어진다.

SOL

스티커를 붙이는 경우의 수를 다 뽑아준다. (2중반복문)

그 중에서, 회전하는 경우를 생각해주면 된다.

• A:(R1,C1) , B:(R2,C2) 라고 했을 때, 4가지 경우의 수가 있다.
• 1.회전을 안하는 경우, 2. A만 회전하는 경우, 3. B만 회전하는 경우, 4. A,B 모두 회전하는 경우
• 이때, 조건을 나눠서 모든 경우를 구해주면 된다!

 

import sys
input= sys.stdin.readline

H,W=map(int,input().split())
N=int(input().rstrip())
stickers=[]
res =0
for i in range(N):
    stickers.append(list(map(int,input().split())))
    
for i in range(N):
    for j in range(i+1,N):
        #첫번째
        r1=stickers[i][0]
        c1=stickers[i][1]
        # 두번째
        r2=stickers[j][0]
        c2=stickers[j][1]
        
        if (r1+r2 <=H and max(c1,c2)<=W) or (max(r1,r2)<=H and c1+c2<=W):
            res=max(res,r1*c1+r2*c2)
        if (c1+r2 <=H and max(r1,c2)<=W) or (max(c1,r2)<=H and r1+c2<=W):
            res=max(res,r1*c1+r2*c2)
        if (c1+c2 <=H and max(r1,r2)<=W) or (max(c1,c2)<=H and r1+r2<=W):
            res=max(res,r1*c1+r2*c2)
        if (r1+c2 <=H and max(c1,r2)<=W) or (max(r1,c2)<=H and c1+r2<=W):
            res=max(res,r1*c1+r2*c2)
print(res)