[BOJ/Python] 16927 두 스티커

📌 문제

[백준] 16927 두 스티커

문제 탐색하기

• H, W: 모눈 종이의 크기
• N: 스티커 수

📌 풀이

코드 설계하기

1. 문제의 Input 받기 (H, W, N)
2. 브루트포스: 스티커의 회전 여부에 따라 조건문으로 나누어 탐색하기

브루트 포스(Brute Force) 알고리즘이란?

완전 탐색 알고리즘의 한 종류로 대부분 조건문과 반복문을 이용하여 가능한 모든 경우의 수를 탐색한다. 모든 경우를 탐색하므로 정확도는 100%에 달할만큼 매우 높지만, 높은 시간 복잡도를 갖는 알고리즘이다.

📌 코드

import sys 

def solution():
    # 1. get input
    H, W = map(int, sys.stdin.readline().split())
    N = int(sys.stdin.readline())
    stickers = list(list(map(int, sys.stdin.readline().split())) for _ in range(N))
    
    # 2. do brute force solution
    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
            
            # 둘 다 회전X
            if (r1+r2 <= H and max(c1, c2) <= W) or (c1+c2 <= W and max(r1, r2) <= H):
                result = max(result, area)
            # 스티커1 회전
            if (c1+r2 <= H and max(r1, c2) <= W) or (r1+c2 <= W and max(c1, r2) <= H):
                result = max(result, area)
            # 스티커2 회전
            if (r1+c2 <= H and max(c1, r2) <= W) or (c1+r2 <= W and max(r1, c2) <= H):
                result = max(result, area)
            # 둘 다 회전
            if (c1+c2 <= H and max(r1, r2) <= W) or (r1+r2 <= W and max(c1, c2) <= H):
                result = max(result, area)
    
    print(result)
    return result
    

solution()