[백준 21761번] 초직사각형 (Python3)

import sys
input = sys.stdin.readline

def m():
  return L[0]*L[1]*L[2]*L[3]

def findmax():
  idx,MAX = -1,-1
  for i in range(4):
    if Q[i]:
      L[i] += Q[i][-1]
      mm = m()
      if MAX < mm:
        MAX = mm; idx = i
      L[i] -= Q[i][-1]
  return idx

N,M = map(int,input().split())
L = [*map(int,input().split())]

Q = [[] for i in range(4)]
for _ in range(N):
  a,b = input().split()
  Q[ord(a)-65].append(int(b))

for i in range(4):
  Q[i].sort()

for _ in range(M):
  idx = findmax()
  print(chr(idx+65),Q[idx][-1])
  L[idx] += Q[idx].pop()

그리디 알고리즘으로 해결하였다.

 

풀이를 설명하면,

1. 현재의 길이를 저장하고, A,B,C,D에 대한 입력값을 분류해서 저장하고, 각 변의 값들을 정렬한다.

2. 현재의 길이에서 A,B,C,D에 대해서 각각의 가장 큰 값에 대해서 어떤 변의 길이에 변화를 주었을 때 부피가 가장 커지는지를 구한다.

3. 2에서 구한 변에 대해서 변의 길이를 늘려주고, 변의 이름과 변화량을 출력한다.

 

아주 직관적인 풀이지만 왜 성립하는지에 대한 엄밀한 증명은 하지 못하였다.

 

 

오늘의 교훈) 왜 풀이가 성립하는지에 대한 증명을 하자