[백준][Python] 16937번 두 스티커

16937번: 두 스티커

 

 

코드

import sys

h, w = map(int,input().split())
n = int(input())
sticker = []
for _ in range(n):
	r,c = map(int,sys.stdin.readline().split())
	sticker.append([r,c])
max_n = 0
for i in range(n):
	r1 = sticker[i][0]
	c1 = sticker[i][1]
	for j in range(i+1,n):
		r2 = sticker[j][0]
		c2 = sticker[j][1]

		if (r1+r2 <= h and max(c1,c2) <= w) or (max(r1,r2) <= h and c1+c2 <= w):
			max_n = max(max_n, r1*c1+r2*c2)
		elif (r1+c2 <= h and max(c1,r2) <= w) or (max(r1,c2) <= h and c1+r2 <= w):
			max_n = max(max_n, r1*c1+r2*c2)
		elif (c1+r2 <= h and max(r1,c2) <= w) or (max(c1,r2) <= h and r1+c2 <= w):
			max_n = max(max_n, r1*c1+r2*c2)
		elif (c1+c2 <= h and max(r1,r2) <= w) or (max(c1,c2) <= h and r1+r2 <= w):
			max_n = max(max_n, r1*c1+r2*c2)
			
print(max_n)

 

설명

이중 for문을 이용해서 두 개의 스티커를 고르는 모든 경우의 수를 확인한다.

두 스티커가 회전할 수 있는 경우의 수는 총 4개이다. 

• 두 스티커 모두 회전하지 않는 경우
• 첫 번째 스티커만 회전하는 경우
• 두 번째 스티커만 회전하는 경우
• 두 스티커 모두 회전하는 경우

위 경우의 수를 모두 고려해서 최댓값을 구해야 한다.

4개의 경우의 수 안에서도 스티커를 위 아래로 붙이는 경우와 옆으로 붙이는 경우를 생각해야 한다.