[백준] 두 스티커 - 파이썬 Python

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

 

1. 완전탐색이 가능한가?

스티커의 개수는 최대 100개이다. 스티커 2개를 고르는 경우의 수는 100*99 = 9900가지이다.

이때 고른 스티커가 모눈종이에 붙일 수 있는지 탐색하는 과정의 시간복잡도를 고려해야 하는데, 스티커마다 90도 회전을 시킬 수 있기 때문에 총 8가지 경우에 대해 탐색한다. (1. 둘다 회전하지 않은 경우 2. 하나만 회전한 경우 3. 다른 하나를 회전한 경우 4. 둘다 회전한 경우) * (1. 가로로 배치 2. 세로로 배치)

따라서 고른 스티커 쌍마다 탐색하는 시간복잡도는 O(1)이다. 

결과적으로 9900가지의 경우 수가 존재하고, 각 경우마다 O(1) 시간복잡도로 탐색하므로 완전탐색이 가능하다.

2. 스티커 붙이기

a. 둘다 회전하지 않은 경우

i. 가로로 배치

가로로 배치하는 경우 `c1+c2 <= W and max(r1, r2) <= H` 조건을 만족하면 스티커 쌍을 붙일 수 있다.

 

ii. 세로로 배치

세로로 배치하는 경우 `r1+r2 <= H and max(c1, c2) <= W` 조건을 만족하면 스티커를 쌍을 붙일 수 있다.

 

위와 같은 경우의 수 판단을 어떤 스티커를 회전하는지에 따라 4번 해주면 된다. 

 

최종코드

import sys

H, W = map(int, input().split())
N = int(input())
stickers = list(list(map(int, input().split())) for _ in range(N))

result = 0
for i in range(N):
    for j in range(i+1, N):
        r1, c1 = stickers[i]
        r2, c2 = stickers[j]
        area = r1*c1 + r2*c2
        
        # 둘다 회전하지 않은 경우
        if (c1+c2 <= W and max(r1, r2) <= H) or (r1+r2 <= H and max(c1, c2) <= W):
            result = max(result, area)
        
        # 첫번째 스티커만 회전한 경우
        if (r1+c2 <= W and max(c1, r2) <= H) or (c1+r2 <= H and max(r1, c2) <= W):
            result = max(result, area)
            
        # 두번째 스티커만 회전한 경우
        if (c1+r2 <= W and max(r1, c2) <= H) or (r1+c2 <= H and max(c1, r2) <= W):
            result = max(result, area)
            
        # 모두 회전한 경우
        if (r1+r2 <= W and max(c1, c2) <= H) or (c1+c2 <= H and max(r1, r2) <= W):
            result = max(result, area)

print(result)