[알고리즘|파이썬] 백준 16937 두 스티커

문제 링크: https://www.acmicpc.net/problem/16937

📌 문제 탐색하기

시간 제한: 2초
메모리 제한: 512 MB

알고리즘 선택

N개의 스티커 중 2개를 골라야하므로 조합으로 푸는 방식으로 접근했을때,

nCr = n!/r!(n-r)!
nC2 = n!/2!(n-2)! = n(n-2)/2

그러므로 O(n^2)이라는 시간 복잡도를 갖게 된다.
문제에서 N의 범위를 1 <= N <= 100 주었기 때문에,
1 <= N^2 <= 10,000, 주어진 시간 2초 안에 사용할 수 있다.

 

주어진 N개의 스티커 중 2개의 조합을 구하고, 조합들 중 H*W 모눈종이에 들어 가는 조합들의 합 중 최댓값을 구하도록 한다.

---

📌 코드 설계하기

1. 주어진 N개의 사이즈 중 H*W 사이즈보다 크지 않은 스티커를 리스트로 받음

2. 받은 리스트로 nC2 조합을 만듦

3. 각 조합이 H*W 에 들어 가는지 확인 후 넓이를 구함

4. 구해진 넓이가 max값이라면 넓이값 업데이트

5. 마지막으로 구해진 넓이값 출력

---

📌 시도 회차 수정 사항

1회차

문제점1. 각 조합이 H*W 에 들어 가는지 확인 이라는 설계가 모호하여 모든 경우의 수를 고려하지 못함.

문제점2. 주어진 N개의 사이즈 중 H*W 사이즈보다 크지 않은 스티커를 리스트로 받음 조건이 잘못 됨. 90도로 회전을 하였을 때 맞을 수도 있므로 입력 단계에서 필요한 값들까지 삭제 함.

 

해결책

H*W 에 들어 가는지 확인을 90도 회전하는 경우까지 고려하여 candidates로 모든 조건을 고려할 수 있도록 수정.

=> 다음부터 설계 단계에서 더 세분화하여 미리 어떻게 조건을 찾을 것인지까지 명시하도록 하자

candidates = [ (a1, b1, a2, b2), (a1, b1, b2, a2), (b1, a1, a2, b2), (b1, a1, b2, a2)]

 

---

📌 정답 코드

import itertools

h, w = map(int, input().split())
n = int(input())
stickers = list()
answer = 0

for _ in range(n):
    a, b = map(int, input().split())
    stickers.append((a, b))
comb = itertools.combinations(stickers, 2)

for (a1, b1), (a2, b2) in comb:
    candidates = [
        (a1, b1, a2, b2),
        (a1, b1, b2, a2),
        (b1, a1, a2, b2),
        (b1, a1, b2, a2)
    ]
    for f1, f2, s1, s2 in candidates:
        # 가로로 나란히 배치
        if f1 + s1 <= h and max(f2, s2) <= w:
            answer = max(answer, f1*f2 + s1*s2)
        # 세로로 나란히 배치
        if f2 + s2 <= w and max(f1, s1) <= h:
            answer = max(answer, f1*f2 + s1*s2)

print(answer)