길이가 n인 나무 막대와 자를 수 있는 위치를 담은 배열 cuts가 주어진다고 가정해 봅시다. 막대는 0부터 n까지의 위치로 표시되며, cuts[i]는 잘라낼 수 있는 위치를 의미합니다. 모든 컷을 반드시 수행해야 하지만, 그 순서는 원하는 대로 변경할 수 있습니다. 이때 한 번의 컷 비용은 잘라야 하는 막대 조각의 길이이며, 전체 비용은 모든 컷 비용의 합입니다. 우리가 구해야 하는 것은 이 컷들의 최소 총 비용입니다.
예를 들어, 입력이 n = 7, cuts = [5,1,4,3]이라면 출력은 16이 됩니다. 컷 순서를 [3,5,1,4]로 정하면 다음과 같이 진행됩니다. 먼저 길이 7의 막대를 위치 3에서 자르므로 비용은 7이고, 이제 길이 3과 4인 두 조각이 생깁니다. 다음으로 위치 5를 자르면 해당 조각의 길이가 4이므로 비용은 4이며, 누적 비용은 7+4=11입니다. 그다음 길이 2의 조각에서 위치 4를 자르므로 비용은 2가 되고, 총 비용은 7+4+2=13입니다. 마지막으로 위치 3을 자르면 비용은 3이며, 최종 비용은 7+4+2+3=16이 됩니다.
해결 접근 방법
이 문제는 구간 동적 계획법(Interval DP)으로 효율적으로 해결할 수 있습니다. 핵심 아이디어는 cost[i][j]를 "cuts[i]와 cuts[j] 사이 구간을 자르는 최소 비용"으로 정의하고, 구간의 길이를 점차 늘려가며 값을 채워나가는 것입니다. 각 구간에 대해 첫 번째로 자를 위치 s를 모두 시도해 보고, 그중 최솟값을 선택합니다. 구간을 자를 때의 비용은 해당 구간의 전체 길이에 양쪽 부분 구간의 최소 비용을 더한 값이 됩니다.
구체적인 단계는 다음과 같습니다.
- cuts 배열을 오름차순으로 정렬한 뒤, 맨 앞에 0을, 맨 뒤에 n을 삽입합니다. 이렇게 하면 전체 막대의 양 끝이 경계로 포함되어 계산이 단순해집니다.
- m := cuts의 크기로 설정합니다.
- cost := m x m 크기의 2차원 행렬을 만들고 0으로 초기화합니다.
- 구간 길이 k를 2부터 m-1까지 반복합니다.
- 시작점 i를 0부터 m-1까지 반복합니다.
- j := i + k로 끝점을 설정합니다.
- 만약 j >= m이면 범위를 벗어나므로 다음 반복으로 넘어갑니다.
- cost[i][j] = (cuts[j] - cuts[i]) + min(cost[i][s] + cost[s][j]), 단 s는 i+1부터 j-1까지의 모든 값입니다.
- 시작점 i를 0부터 m-1까지 반복합니다.
- 최종적으로 cost[0][m-1]을 반환합니다. 이것이 전체 막대를 자르는 최소 비용입니다.
구현 예제
아래 파이썬 코드를 통해 더 잘 이해해 보겠습니다.
def solve(n, cuts):
cuts = [0] + sorted(cuts) + [n]
m = len(cuts)
cost = [[0]*m for _ in range(m)]
for k in range(2, m):
for i in range(m):
j = i + k
if j >= m:
continue
cost[i][j] = (cuts[j]-cuts[i]) + min(cost[i][s] + cost[s][j] for s in range(i+1, j))
return cost[0][m-1]
n = 7
cuts = [5,1,4,3]
print(solve(n, cuts))입력
7, [5,1,4,3]
출력
16
이 알고리즘의 시간 복잡도는 O(m³)이며, 여기서 m은 컷의 개수에 2를 더한 값입니다. 공간 복잡도는 2차원 DP 테이블을 사용하므로 O(m²)입니다. 컷의 개수가 많지 않은 경우 이 방법으로 충분히 효율적으로 문제를 해결할 수 있습니다.