[백준] 16937 두 스티커

문제

• 크기가 HxW인 모눈종이에 N개 중 2개의 스티커를 붙인다.
  • 1 <= H, W, N <= 100 
• 두 스티커는 겹치면 안되고, 모눈 종이를 벗어나서도 안되고, 비스듬하게 붙일 수도 없다.
• 단, 90도 회전은 가능할 때, 두 스티커가 붙여진 넓이의 최댓값은?
• 두 스티커를 붙일 수 없는 경우에는 0을 출력

 

 

풀이

• 스티커 2개만 붙이면 되니까 100개 중 2개 조합을 완전 탐색으로 풀 수 있다.
• 경우의 수는 총 8가지
  • 옆으로 나란히 붙이고, ( 둘 다 회전 안할 때, 1번만 회전할 때, 2번만 회전할 때, 둘 다 회전할 때)
  • 위아래로 붙이고, ( 둘 다 회전 안할 때, 1번만 회전할 때, 2번만 회전할 때, 둘 다 회전할 때)

H, W = map(int, input().split())
N = int(input())
stickers = []
for _ in range(N):
    a, b = map(int, input().split())
    stickers.append((a, b))

answer = 0          # 정답 변수
for i in range(N):
    h1, w1 = stickers[i]
    for j in range(i+1, N):
        h2, w2 = stickers[j]
        # 옆으로 나란히 붙이기
        if (w1 + w2 <= W and max(h1, h2) <= H) or (w1 + h2 <= W and max(h1, w2) <= H) or (h1 + h2 <= W and max(w1, w2) <= H) or (h1 + w2 <= W and max(w1, h2) <= H) :
            answer = max(answer, h1*w1 + h2*w2)

        # 위아래로 붙이기
        elif (h1 + h2 <= H and max(w1, w2) <= W) or (h1 + w2 <= H and max(w1, h2) <= W) or (w1 + w2 <= H and max(h1, h2) <= W) or (w1 + h2 <= H and max(h1, w2) <= W) :
            answer = max(answer, h1*w1 + h2*w2) 
            
print(answer)

 

(추가)

• 처음부터 붙일 수 없는 스티커를 제외하고 길이 확인을 간단하게 하려고 했는데, 6%에서 실패한다. 

H, W = map(int, input().split())
N = int(input())
stickers = []
for _ in range(N):
    a, b = map(int, input().split())
    # 붙일 수 없는 스티커는 제외한다.
    if (a > H and a > W) or (b > H and b > W):  continue
    stickers.append((a, b))

answer = 0          # 정답 변수
n = len(stickers)   # 붙일 수 있는 스티커 개수

for i in range(n):
    h1, w1 = stickers[i]
    for j in range(i+1, n):
        h2, w2 = stickers[j]
        # 옆으로 나란히 붙이기
        if w1 + w2 <= W or w1 + h2 <= W or h1 + h2 <= W or h1 + w2 <= W :
            answer = max(answer, h1*w1 + h2*w2)
        # 위아래로 붙이기
        elif h1 + h2 <= H or h1 + w2 <= H or w1 + w2 <= H or w1 + h2 <= H :
            answer = max(answer, h1*w1 + h2*w2)

print(answer)

 

• 반례 찾았다. 회전했을 때 최대 길이를 검사해줘야 한다!

6 7
2
5 3
2 7

 

 

 

References

• 백준 16937번
• 2023.04.27 오늘의 문제