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에서 구한 변에 대해서 변의 길이를 늘려주고, 변의 이름과 변화량을 출력한다.
아주 직관적인 풀이지만 왜 성립하는지에 대한 엄밀한 증명은 하지 못하였다.
오늘의 교훈) 왜 풀이가 성립하는지에 대한 증명을 하자