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

문제 번호 : 16936

문제 출처 : https://www.acmicpc.net/problem/16937

16937번: 두 스티커

 

---

---

Code

import sys


def able(height, width, row, col):
    if row <= height and col <= width:
        if row <= width and col <= height:
            return 3
        else:
            return 1
    elif row <= width and col <= height:
        return 2
    else:
        return 0


h, w = map(int, input().split())
n = int(input())
stickers = [list(map(int, sys.stdin.readline().split())) for _ in range(n)]
result = 0

for i in range(len(stickers)):
    r, c = stickers[i][0], stickers[i][1]
    way = able(h, w, r, c)
    if way > 0:
        if way == 1:
            new_hw = [h-r, w, h, w-c]
        elif way==2:
            new_hw = [h-c, w, h, w-r]
        else:
            new_hw = [h-r, w, h, w-c, h-c, w, h, w-r]

        for sticker in stickers[i+1:]:
            new_r, new_c = sticker[0], sticker[1]
            for j in range(0, len(new_hw), 2):
                if able(new_hw[j], new_hw[j+1], new_r, new_c) > 0:
                    result = max(r*c + new_r * new_c, result)
print(result)

Idea

1. 스티커의 한 변의 길이가 모눈종이의 높이보다 작거나 같고 다른 한 변의 길이가 모눈종이의 너비보다 작거나 같으면 스티커를 모눈 종이에 붙일 수 있다.
   단순히 붙일 수 있는지 확인하는 것은 max(r, c) < max(h, w) and min(r, c) < min(h, w) 로 구현하면 된다.
2. 붙일 수 있는 스티커면 일단 붙인다.
   

   

   10 x 10 모눈종이에 6 x 7 스티커가 붙어 있는 경우

3.  1번 영역에 스티커가 붙어 있으면 2번 영역 + 4번 영역, 3번 영역 + 4번 영역 두 가지 위치에 붙일 수 있다.
   따라서 이 때 새로운 크기를 가진 모눈 종이가 생긴다고 생각한다.
   이 새 모눈 종이들의 높이와 너비를 new_hw 리스트에 저장한다.
4. 현재 붙은 스티커 이후의 스티커들이 새 모눈 종이에 붙일 수 있는지를 판별하고 그 때의 넓이가 더 커지면 result를 갱신한다. 

처음에는 stickers를 넓이를 기준으로 내림차순으로 정렬한 후 두 스티커가 붙게 되면 무조건 최대값이니까 break문을 사용해서 최대한 반복문을 덜 돌게 하려고 노력했고 입력 예제 입력들은 모두 통과가 되는데 코드 제출하니까 "틀렸습니다."라고 나왔다.