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

16937번: 두 스티커

문제

크기가 주어진 모눈종이에 2개의 스티커를 골라 붙혔을 때 넓이가 가장 큰 경우의 값을 구하는 문제이다.

---

풀이

• 1 ≤ H, W, N ≤ 100
• 1 ≤ Ri, Ci ≤ 100

조건이 다음과 같으므로 모든 경우의 수를 탐색해도 괜찮다 판단하여 브루트 포스를 사용하였다.

1. 브루트 포스

브루트 포스란 조합 가능한 모든 문자열을 하나씩 대입해 보는 방식으로 암호를 해독하는 방법이다.

 

2. 아이디어

먼저 가능한 경우의 수를 따져보았다. 2개의 스티커를 뽑고 각각의 스티커는 회전할 수 있으므로,

모두 회전하지 않은경우

 

1번만 회전한 경우

2번만 회전한경우

모두 회전한경우

위의 그림과 같이 4가지의 경우의 수가 나오게된다. 그리고 각각의 경우의 수 마다 스티커를 가로로 배열할 지 세로로 배열할지를 생각하면 총 8가지의 경우의 수가 나오게 된다. 따라서 8가지의 경우의수 중 모눈종이의 길이를 넘지 않는 경우의수를 골라 넓이를 계산하였다.

 

if (r1+r2 <= W and max(c1, c2) <= H) or (max(r1, r2) <= W and c1 + c2 <= H):
	ans = max(ans, r1*c1 + r2*c2)

if (c1+r2 <= W and max(r1, c2) <= H) or (max(c1, r2) <= W and r1+c2 <= H):
	ans = max(ans, r1*c1 + r2*c2)

if (r1 + c2 <= W and max(c1, r2) <= H) or (max(r1, c2) <= W and c1 + r2 <= H):
	ans = max(ans, r1*c1 + r2*c2)

if (c1 + c2 <= W and max(r1, r2) <= H) or (max(c1, c2) <= W and r1 + r2 <= H):
	ans = max(ans, r1*c1 + r2*c2)​

---

코드

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

N = int(input())

sticker = []
ans = 0

for i in range(N):
    sticker.append(list(map(int, input().split())))


for i in range(N):
    for j in range(i+1, N):
        r1, c1 = sticker[i]
        r2, c2 = sticker[j]

        if (r1+r2 <= W and max(c1, c2) <= H) or (max(r1, r2) <= W and c1 + c2 <= H):
            ans = max(ans, r1*c1 + r2*c2)

        if (c1+r2 <= W and max(r1, c2) <= H) or (max(c1, r2) <= W and r1+c2 <= H):
            ans = max(ans, r1*c1 + r2*c2)

        if (r1 + c2 <= W and max(c1, r2) <= H) or (max(r1, c2) <= W and c1 + r2 <= H):
            ans = max(ans, r1*c1 + r2*c2)

        if (c1 + c2 <= W and max(r1, r2) <= H) or (max(c1, c2) <= W and r1 + r2 <= H):
            ans = max(ans, r1*c1 + r2*c2)

print(ans)