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

숨·2024년 8월 5일

📌 문제 탐색하기

H : 모눈종이의 세로 길이 ( $1 ≤ H ≤ 100$ )
W : 모눈종이의 가로 길이 ( $1 ≤ W ≤ 100$ )
N : 스티커의 수 ( $1 ≤ N ≤ 100$ )
R : 스티커의 세로 길이 ( $1 ≤ R_{i} ≤ 100$ )
C : 스티커의 가로 길이 ( $1 ≤ C_{i} ≤ 100$ )

✅ 입력 조건
1. 첫번째 줄 H, W 입력
2. 두번째 줄 N 입력
3. N번 반복해 R, C 입력
✅ 출력 조건
1. 2개의 스티커가 붙여진 넓이의 최댓값 출력
2. 2개의 스티커를 붙일 수 없다면 0 출력

전체 크기가 H×W이면서, 한 칸의 크기가 1×1인 모눈종이가 있다.
N개의 스티커가 있을 때, 2개의 스티커를 선택해서 붙였을 경우에 얻을 수 있는 가장 큰 넓이를 찾아 출력하는 문제이다.

스티커를 붙일 때,
1) 격자의 선과 일치 = 비뚤어지지 않고,
2) 서로 겹치지 않게 붙이면서,
3) H×W 크기를 벗어나지 않아야 한다.
4) 스티커가 접하는 것을 가능하며,
5) 필요한 경우 스티커를 90도 회전시켜서 붙이는 것도 가능하다.

~~N개의 스티커를 입력받을 때, 각 스티커의 크기가 H×W보다 작은 경우만 리스트에 추가해준다.~~ → 틀려서 모두 입력받도록 변경

스티커들 중 2개를 선택해서 모눈종이에 붙이는 경우들이 위의 조건들을 충족하는지 확인한다.
붙이는 경우는 다음과 같은 유형이 있을 수 있다.
1. 위아래로 붙이기
1-1. 세로 길이의 합이 H보다 작아야 한다
1-2. 가로 길이 중 가장 긴 길이가 W보다 작아야 한다
2. 나란히 붙이기
2-1. 가로 길이의 합이 W보다 작아야 한다
2-2. 세로 길이 중 가장 긴 길이가 H보다 작아야 한다

90도 회전시키는 경우는 R과 C의 순서만 바꿔주면 되므로,
입력받은 N개의 (R, C) 조합과 (C, R) 조합을 함께 조건에 충족하는지 검사해준다.

이중 for문으로 2개의 스티커를 검사해준다.
스티커를 입력할 때 크기 검사로 걸러낸 스티커가 있기 때문에 전체 스티커 리스트 길이를 따로 계산해준다. (n으로 정의)

첫번째 for문 → 스티커 리스트의 인덱스 0부터 n-1을 반복
두번째 for문 → 첫번째 for문의 다음 인덱스부터 n-1까지 반복
위에 작성한 유형에 따른 검사 방법 구현

가능한 시간복잡도

스티커 조합 찾는 이중 for문 → $O(n * \frac{n-1}{2}) = O(n^2)$

최종 시간복잡도
$O(n^2)$ 으로 최악의 경우 $O(10000)$ 이다.
이는 2초 내로 계산이 가능할 것 같다.

알고리즘 선택

브루트포스로 모든 스티커 조합을 확인해서 조건에 맞는 경우를 찾아 최대 넓이를 갱신하며 구하기

📌 코드 설계하기

H, W 입력
N 입력
N번 반복해 R, C 입력
조건에 맞는 스티커 조합을 찾아 최대 넓이 갱신

📌 시도 회차 수정 사항

1회차

# N번 반복해 R, C 입력
for _ in range(N):
    R, C = map(int, input().split())
    # 모눈종이보다 크면 무시
    if (R <= H and C <= W) or (R <= W and C <= H):
        stickers.append((R, C))

# 최대 넓이 변수 정의
max_area = 0

# 전체 스티커 수 정의 (제외한 스티커 크기가 있기 때문에 따로 계산)
n = len(stickers)

for i in range(n):
    # 첫번째 스티커
    R1, C1 = stickers[i]
    for j in range(i + 1, n):
        # 두번째 스티커
        R2, C2 = stickers[j]
        # 위아래 붙이기
        if (R1 + R2 <= H) \
                or (R1 + C2 <= H) \
                or (C1 + C2 <= H) \
                or (C1 + R2 <= H):
            max_area = max(max_area, R1 * C1 + R2 * C2)

        # 나란히 붙이기
        elif (R1 + R2 <= W) \
                or (R1 + C2 <= W) \
                or (C1 + C2 <= W) \
                or (C1 + R2 <= W):
            max_area = max(max_area, R1 * C1 + R2 * C2)

결과
입력 받을 때 스티커 크기 중 하나라도 H, W 크기보다 크면 저장하지 않는 방식으로 구현해서 조건문을 깔끔하게 만들고 싶었다.
생각해보니 스티커를 회전했을 때를 같이 고려해주지 않아 틀렸다는 결과를 얻었던 것 같다.
이중 for문 안의 조건문에서 최대 길이를 고려하는 식으로 해결했다.

📌 정답 코드

import sys

input = sys.stdin.readline

# H, W 입력
H, W = map(int, input().split())

# N 입력
N = int(input())

# 스티커 크기 저장할 리스트 정의
stickers = []

# N번 반복해 R, C 입력
for _ in range(N):
    R, C = map(int, input().split())
    stickers.append((R, C))

# 최대 넓이 변수 정의
max_area = 0

# 전체 스티커 수 정의 (제외한 스티커 크기가 있기 때문에 따로 계산)
n = len(stickers)

for i in range(n):
    # 첫번째 스티커
    R1, C1 = stickers[i]
    for j in range(i + 1, n):
        # 두번째 스티커
        R2, C2 = stickers[j]
        # 위아래 붙이기
        if (R1 + R2 <= H and max(C1, C2) <= W) \
                or (R1 + C2 <= H and max(C1, R2) <= W) \
                or (C1 + C2 <= H and max(R1, R2) <= W) \
                or (C1 + R2 <= H and max(R1, C2) <= W):
            max_area = max(max_area, R1 * C1 + R2 * C2)

        # 나란히 붙이기
        elif (R1 + R2 <= W and max(C1, C2) <= H) \
                or (R1 + C2 <= W and max(C1, R2) <= H) \
                or (C1 + C2 <= W and max(R1, R2) <= H) \
                or (C1 + R2 <= W and max(R1, C2) <= H):
            max_area = max(max_area, R1 * C1 + R2 * C2)

# 정답 출력
print(max_area)