문제
접근
그리디 알고리즘이다.
4개 숫자의 곱을 최대화하는게 목적이다.
이 때 주어지는 카드 중에 K개만을 선택해야 한다.
결국 주어진 카드 중에 부피를 최대화할 수 있는 카드를 선택해야 한다.
이를 위해서 주어지는 카드들을 문자 A,B,C,D에 따라 나누고, 각 그룹별로 정렬해준다.
각 문자 그룹에서 가장 큰 값들, 즉 4개의 값만 연산해보고 비교하면 된다.
이 과정을 K번 반복하면 된다.
코드
- 파이썬 코드
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
import sys
input = sys.stdin.readline
def calcSize(arr):
ans = 1
for item in arr:
ans *= item
return ans
dic = {0:'A', 1:'B', 2:'C', 3:'D'}
n, k = map(int,input().split())
nowLen = list(map(int, input().split()))
change = [[] for _ in range(4)]
for _ in range(n):
item, size = input().split()
if item == 'A':
change[0].append(int(size))
elif item == 'B':
change[1].append(int(size))
elif item == 'C':
change[2].append(int(size))
else:
change[3].append(int(size))
for i in range(4):
change[i].sort()
maxSize = calcSize(nowLen)
for _ in range(k):
maxIdx = -1
for i in range(4):
if len(change[i]):
nowLen[i] += change[i][-1]
tmpSize = calcSize(nowLen)
nowLen[i] -= change[i][-1]
if maxSize < tmpSize:
maxSize = tmpSize
maxIdx = i
changeLen = change[maxIdx].pop(-1)
nowLen[maxIdx] += changeLen
print(dic[maxIdx], changeLen)