동적계획법(DP) 대표문제2 - ROD CUTTING(막대기 자르기)

동적계획법(Dynamic Programming, DP)는 가장 많이 쓰이는 알고리즘 기법이자 기초이다. 하지만 그만큼 다양한 응용과 아이디어가 필요해서 완벽하게 익히기도 어렵다. 이론은 듣기에 간단하지만 문제에 따라 응용이 매우 어려운 것이다. 때문에 다양한 문제를 풀어보며 직접 익히는 방법밖에는 없다. 특히, 점화식을 세우고 점화식에 따라 DP 해법을 저장하는 배열을 선언하는 연습을 많이 해 봐야 할 것이다.

동적계획법을 사용해 풀 수 있는 대표 문제 중 두번째로 ROD CUTTING(막대기 자르기) 문제에 대해 소개하려고 한다. 문제를 푸는데 사용한 언어는 java 이다.

이 문제를 보기 전에, 동적계획법에 대한 아무런 사전 지식이 없다면 아래 포스팅을 먼저 참고 바란다.

[동적계획법 풀이 대한 간략한 소개 : http://www.leafcats.com/72 ]

문제 : ROD CUTTING - 막대기 자르기

내용 : 

---

길이가 N인 막대기가 있다. 막대기를 길이가 자연수가 되도록 여러 조각으로 자를 수 있다.

막대기는 자르는 길이에 따라 값이 정해져 있다. 막대를 자르는 값어치의 합이 최대가 되게끔 막대기를 자르자.

예를 들어, 길이가 4인 막대기를 자를 때, 길이 별 받을 수 있는 값이 아래와 같다고 하자.

Length	1	2	3	4
Cost	1	5	8	9

이 경우에 길이 2에 cost 5인 막대기 두 개가 되게끔 자르면 전체 값어치가 10으로 최대로 값을 받을 수 있을 것이다.

첫 줄에 막대기 길이 N(1<= N <= 3000)이 주어지고,

두번째 줄에 1000이하의 자연수 N 개가 공백으로 구분되어 주어진다. i번째 자연수는 길이 i 막대기의 값을 의미한다.

첫 줄에 값어치 합이 최대가 되도록 막대기를 자를 때, 값어치 합을 출력한다.

---

예제 입력 : 

4

1 5 8 9

예제 출력 : 10

---

풀이 :

대표적인 동적계획법 문제이다. 문제의 아이디어는 다음과 같다. 

길이 N의 막대기를 자르는 경우의 최대값은 다음 값들 중 최대가 되는 값일 것이다. 

길이 N-1의 막대를 자르는 최대값에 길이 1의 막대의 값을 더하는 경우.

길이 N-2의 막대를 자르는 최대값이 길이 2의 막대의 값을 더하는 경우.

...

길이 0의 막대를 자르는 최대값에 길이 N의 막대의 값을 더하는 경우. 즉, 막대를 자르지 않고 파는 경우.

예를 들어 길이 4의 막대의 최대값은 아래 구해지는 값들 중 최대를 취하면 될 것이다.

길이 3의 막대로 받을 수 있는 최대값에 길이 1 막대의 값을 더한 값.

길이 2의 막대로 받을 수 있는 최대값에 길이 2 막대의 값을 더한 값.

...

길이 4 막대 자체의 값.

길이 4의 막대의 최대값을 구하기 위해서 길이 1,2,3 막대의 최대값 먼저 구해 이를 사용하게 된다.

이렇게 작은 문제의 해답으로 큰 문제를 해결 하는 것이 동적계획법의 기본 개념이다.

이것을 점화식으로 표현하면, 길이 n의 막대로 받을 수 있는 최대 가치는 다음과 같다.

길이 n 막대의 값을 구하기 위해, 길이 1부터 n까지의 값을 모두 이용해야 하기 때문에 이 문제는 시간복잡도 Θ(N^2)을 가진다. 1차원배열 하나로 해결할 수 있기 때문에, 공간복잡도는 Θ(N)범위 내에서 해결할 수 있다.

주어진 문제의 N 값이 3000개 이내이므로 N^2의 범위에서 충분히 답을 구할 수 있다.

(이렇게 어떤 문제에서 주어진 입력값의 양으로 지금 접근하고자 하는 방법으로 풀었을 때에 시간 내에 답이 나올 수 있는지, 메모리 제한을 넘지 않을 수 있는지를 판단하는 것이 매우 중요하다.)

이를 자바 코드로 구현하면 다음과 같다.

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
 
public class rodCutting {
    
    private static int N;
    private static BufferedReader br;
    private static StringTokenizer st;
    
    private static int [] partPrice;
    private static int [] maxPricePerLength;
    
    public static void main(String[] args) throws NumberFormatException, IOException {
        
        br = new BufferedReader(new InputStreamReader(System.in));
        
        N = Integer.parseInt(br.readLine());
        
        partPrice = new int [N+1];
        maxPricePerLength = new int [N+1];
        
        st = new StringTokenizer(br.readLine(), " ");
        for (int i = 1; i <= N; i++) {
            partPrice[i] = Integer.parseInt(st.nextToken());
        }
        
        br.close();
        
        for (int i = 1; i <= N; i++) {
            int max = 0;
            for (int j = 1; j <= i; j++) {
                max = Math.max(max, partPrice[j] + maxPricePerLength[i-j]);
            }
            maxPricePerLength[i] = max;
        }
        
        System.out.println(maxPricePerLength[N]);
    }
 
}
 

참고로 알고리즘을 코드로 구현할 때, 최대한 짧게 코드를 줄이는 경우가 많다. 개인적으로 현업 개발자의 관점에서 극한으로 줄여서 압축된 코드는 코드 품질이 좋지 못하다고 보인다. 내가 개발한 코드는 앞으로 수많은 사람들이 유지보수나 리뷰를 위해 볼 수 있기 때문이다. 

때문에 코드 성능에 차이가 없다면 될 수 있으면 가독성이 좋게끔 코딩 하는 습관이 매우 중요하다.