백준 16937 두 스티커 | Brute Force

 

 

백준 문제집 16937 풀이

 

 

문제:

 

 

 

즉, 일정한 면적이 주어지고 n개의 스티커와 각 크기들이 주어졌을 때

2개의 스티커만 골라 최대의 면적을 만드는 문제다.

 

 

처음에 회전 부분까지 생각했을 때,

실제로 회전시켜서 구하는 방법까지 구현했어서

이게 맞나? 란 생각이 들었다.

 

 

분명 더 쉽운 방법이 있을거 같아서

다시 문제로 돌아가 천천히 읽었다.

 

 

여기서의 핵심은

스티커의 회전의 값이 직접 필요한게 아니라

그냥 돌렸다고 전제해도 무방하다는 것이다.

 

 

그 부분에서 아이디어를 얻어

for loop 을 사용해 전체 4가지 케이스 별로

if 구절을 넣어 나눠주었다.

 

 

1. sticker 1, 2 둘 다 회전을 하지 않는 경우

2. sticker 1 회전할 경우

3. sticker 2 회전할 경우

4. sticker 1, 2 둘 다 회전할 경우

 

 

1번의 경우 둘 다 회전을 하지 않기 때문에

가장 큰 변을 가진 스티커를 찾아 (max 함수 사용)

곱한 수를 더해주면 끝이다.

 

2, 3번의 경우 밑변과 사이드변의 길이를 바꿔주면 된다.

가장 큰 변을 찾는 부분은 1번과 동일하다.

 

4번의 경우 두 sticker 모두 밑변과 사이드변의

길이를 바꿔서 최대치를 찾아 곱해 더해주면 끝!

 

 

 

Time complexity: O(n**2)

Space complexity: O(1)

 

 

여기서의 시간, 공간 복잡도는 위와 같은데,

 

 

시간 복잡도의 경우, for loop 안에 for loop 을 사용했기 때문에

square 로 Big O 계산식으로 표기를 할 수 있겠다.

 

# Input info
h, w = map(int, input().split())
n = int(input())
stickers = [list(map(int.input().split())) for _ in range(n)]

# Return to the answer
result = 0

# multiple for loop to find
for i in range(n):
    for j in range(i+1, n):
        r1, c1 = stickers[i]
        r2, c2 = stickers[j]

		# No rotate sticker 1, 2
        if (r1 + r2 <= h and max(c1, c2) <= w) or (max(r1, r2) <= h and c1 + c2 <= w):
            result = max(result, r1 * c1 + r2 * c2)
            
        # Rotate the sticker 1
        if (c1 + r2 <= h and max(r1, c2) <= w) or (max(c1, r2) <= h and r1 + c2 <= w):
            result = max(result, r1 * c1 + r2 * c2)
            
        # Rotate the sticker 2
        if (r1 + c2 <= h and max(c1, r2) <= w) or (max(r1, c2) <= h and c1 + r2 <= w):
            result = max(result, r1 * c1 + r2 * c2)
            
        # Rotate the sticker 1, 2
        if (c1 + c2 <= h and max(r1, r2) <= w) or (max(c1, c2) <= h and r1 + r2 <= w):
            result = max(result, r1 * c1 + r2 * c2)

# answer output
print(result)

 

 

 

Brute Force 방식으로 풀었지만, 시간 복잡도를 줄이려면

n개의 스티커에 대한 각 면적값을 구한 후,

내림차순 정열을 사용해서 해당 길이가 부합한지를 판단한다면

훨씬 줄어들 것으로 생각된다. (O(logn) 예상)