길이가 p이고 너비가 q인 보드가 하나 있다고 가정해 봅시다. 이 보드를 총 p×q개의 정사각형 조각으로 잘라야 하며, 이때 전체 자르기 비용을 최소화하는 것이 목표입니다. 각 가로·세로 선을 자를 때 드는 비용은 미리 주어집니다.
예를 들어 입력이 다음과 같다면,
X_slice = [3, 2, 4, 2, 5], Y_slice = [5, 2, 3]
출력 결과는 65가 됩니다.
접근 방식: 그리디(Greedy) 알고리즘
핵심 아이디어는 간단합니다. 비용이 큰 컷부터 먼저 실행하는 것입니다.
어떤 선을 자를 때 그 비용은 현재까지 만들어진 직교 방향의 조각 수만큼 곱해져 누적됩니다. 따라서 비싼 컷일수록 조각 수가 아직 적을 때, 즉 가능한 한 빨리 잘라야 총비용을 줄일 수 있습니다.
알고리즘 단계
- 결괏값 res를 0으로 초기화하고, horizontal과 vertical을 각각 1로 설정합니다.
- X_slice와 Y_slice를 내림차순으로 정렬합니다.
- 두 배열을 순회하며 더 큰 비용의 컷을 먼저 처리합니다.
- X_slice[i] > Y_slice[j]라면: res에 X_slice[i] × vertical을 더하고 horizontal을 1 증가시킵니다.
- 그렇지 않다면: res에 Y_slice[j] × horizontal을 더하고 vertical을 1 증가시킵니다.
- 한쪽 배열을 모두 처리했다면, 남은 원소들의 합에 해당 방향의 조각 수를 곱해 res에 더합니다.
- 최종 res를 반환합니다.
구현 예제
아래 코드를 통해 동작 과정을 더 쉽게 이해할 수 있습니다.
def minCost(X_slice, Y_slice, m, n): res = 0 X_slice.sort(reverse=True) Y_slice.sort(reverse=True) horizontal = 1 vertical = 1 i = 0 j = 0 while i < m and j < n: if X_slice[i] > Y_slice[j]: res += X_slice[i] * vertical horizontal += 1 i += 1 else: res += Y_slice[j] * horizontal vertical += 1 j += 1 total = 0 while i < m: total += X_slice[i] i += 1 res += total * vertical total = 0 while j < n: total += Y_slice[j] j += 1 res += total * horizontal return res m = 6 n = 4 X_slice = [3, 2, 4, 2, 5] Y_slice = [5, 2, 3] print(minCost(X_slice, Y_slice, m - 1, n - 1))
입력
[3, 2, 4, 2, 5], [5, 2, 3]
출력
65
동작 원리 살펴보기
위 예제에서 m = 6, n = 4이므로 세로 방향 컷(X_slice)은 5개, 가로 방향 컷(Y_slice)은 3개입니다. 두 배열을 내림차순으로 정렬하면 X_slice = [5, 4, 3, 2, 2], Y_slice = [5, 3, 2]가 됩니다.
비용이 큰 컷부터 차례대로 처리하면, 처음에는 조각이 1개뿐이므로 큰 비용도 배수 없이(×1) 그대로 반영됩니다. 컷을 진행할수록 직교 방향의 조각 수가 늘어나지만, 이미 비싼 컷들은 처리된 상태이므로 큰 배수가 적용되는 것은 상대적으로 저렴한 컷들뿐입니다. 이러한 그리디 선택 덕분에 전체 비용 65라는 최솟값을 얻을 수 있습니다.
시간 복잡도
정렬에 O(m log m + n log n), 이후 순회에 O(m + n)이 소요되므로 전체 시간 복잡도는 O(m log m + n log n)입니다.