박스 종류를 나타내는 2차원 배열 boxTypes가 있다고 가정해 보겠습니다. boxTypes[i]는 두 개의 요소, 즉 [i번째 타입 박스의 개수, 박스당 단위 수]로 구성됩니다. 여기에 트럭에 실을 수 있는 최대 박스 개수를 의미하는 값 k도 주어집니다. 실리는 박스 개수가 k를 초과하지 않는 한 어떤 박스든 자유롭게 선택할 수 있으며, 우리의 목표는 트럭에 실을 수 있는 최대 총 단위 수를 구하는 것입니다.
예를 들어 입력이 boxTypes = [[2,4],[3,3],[4,2]], k = 6이라면 출력은 19가 됩니다. 그 이유는 다음과 같습니다.
1번 타입의 박스 2개 — 각 박스에 4개의 단위 포함
2번 타입의 박스 3개 — 각 박스에 3개의 단위 포함
3번 타입의 박스 4개 — 각 박스에 2개의 단위 포함
k = 6이므로 단위 수가 많은 1번과 2번 타입의 박스는 모두 실을 수 있고, 3번 타입은 1개만 실을 수 있습니다. 따라서 (2×4) + (3×3) + (1×2) = 8 + 9 + 2 = 19개의 단위를 실을 수 있습니다.
접근 방법: 그리디 알고리즘
이 문제는 그리디(Greedy) 방식으로 효율적으로 해결할 수 있습니다. 핵심 아이디어는 간단합니다. 바로 단위 수가 많은 박스부터 우선적으로 싣는 것입니다. 박스당 단위 수를 기준으로 내림차순 정렬한 뒤, 트럭의 용량 k가 허용하는 만큼 차례대로 채워 나가면 최적의 결과를 얻을 수 있습니다.
구체적인 해결 절차는 다음과 같습니다.
박스당 단위 수(i[1])를 기준으로 boxTypes를 내림차순 정렬합니다.
total := 0, fill := 0으로 초기화합니다.
boxTypes의 각 요소 i에 대해 다음을 반복합니다.
fill + i[0] <= k 인 경우:
fill := fill + i[0]
total := total + i[0] × i[1]
그렇지 않은 경우(남은 용량이 부족한 경우):
total := total + (k − fill) × i[1]
반복문을 종료합니다.
total을 반환합니다.
예시 코드 (Python)
아래 구현 예제를 통해 더 잘 이해해 보겠습니다.
def solve(boxTypes, k):
boxTypes.sort(key = lambda x : x[1], reverse = True)
total = 0
fill = 0
for i in boxTypes:
if fill + i[0] <= k:
fill += i[0]
total += i[0] * i[1]
else:
total += (k - fill) * i[1]
break
return total
boxTypes = [[2,4],[3,3],[4,2]]
k = 6
print(solve(boxTypes, k))
입력
[[2,4],[3,3],[4,2]], 6
출력
19