[BOJ] 두 스티커 (no.16937)

문제

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

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

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

입력

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

출력

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

🤔 생각

• 그림판에 쓰면서 구상한 것...

• 일단 스티커가 2개니까, 놓는 경우를 전부 다 조건문으로 돌려서 처리하면 된다.

• 격자 범위를 초과하는 경우만 필터링해주면 된다.

📌 내 풀이

from itertools import combinations
import sys
input = sys.stdin.readline
print = sys.stdout.write

h,w = map(int, input().split())
n = int(input())
sticker = tuple(tuple(map(int, input().split())) for _ in range(n))
ans = 0

for comb in combinations(sticker, 2):
    a,b = comb
    ax, ay, bx, by = a[0], a[1], b[0], b[1]

    # 가로 x 가로
    if ax + bx <= w and max(ay, by) <= h:
        ans = max(ans, (ax*ay)+(bx*by))
        continue
    # 가로 회전
    elif ax + by <= w and max(ay, bx) <= h:
        ans = max(ans, (ax*ay)+(bx*by))
        continue
    # 세가
    elif ay + bx <= w and max(ax, by) <= h:
        ans = max(ans, (ax*ay)+(bx*by))
        continue
    # 세세
    elif ay + by <= w and max(ax, bx) <= h:
        ans = max(ans, (ax*ay)+(bx*by))
        continue
    # 가로 x 가로
    elif max(ax, bx) <= w and ay + by <= h:
        ans = max(ans, (ax*ay)+(bx*by))
        continue
    # 가로 회전
    elif max(ax, by) <= w and ay + bx <= h:
        ans = max(ans, (ax*ay)+(bx*by))
        continue
    # 세가
    elif max(ay, bx) <= w and ax + by <= h:
        ans = max(ans, (ax*ay)+(bx*by))
        continue
    # 세세
    elif max(ay, by) <= w and ax + bx <= h:
        ans = max(ans, (ax*ay)+(bx*by))
        continue

print("%d" % ans)

✔ 회고

• 직관적이고 무식한 풀이였다.
• 반복문으로 충분히 단축할 수 있다!