동적계획법 - 막대자르기

문제

하나의 막대기가 있다. 막대기 길이에 따라 가격이 다르다.

최고의 수익을 얻도록 막대기를 자르라.

 

입력

막대의 길이, 길이 별 가격

 

출력

최고 수익

 

---

풀이

- 길이가 4인 막대가 있다고 할 때 나올 수 있는 경우의 수는 아래와 같다

 

막대기를 1만큼 자른게 R1이라고 했을 때

최종 가격은 R1+R1+R1+R1 , R1+R3 , R2+R2 , R4 중 최적의 값이 된다.

 

여기서 R3은 R1+R2의 조합으로 볼 수 있고, R2도 마찬가지로 R1+R1의 조합으로 볼 수 있다

즉 각각의 길이에 맞는 최대값을 구해놓으면 최적의 값 계산이 가능하다.

 

ex)

R1은 더 자를 수 없으니 1이 최대 값이고

R2는 R1+R1의 조합인 2와 자르지 않은 가격인 5를 비교해 더 큰 값인 5 가 된다

R3은 R1+R2(1+5)인 6과 자르지 않은 가격인 8을 비교해 8이 된다

마지막으로 R4는 R1+R3(1+8), R2+R2(5+5), 자르지않은 가격 9 세개를 비교해 가장 큰 10이 된다.

 

이런식으로 공통적인 부분 문제를 도출해서 풀 수 있다.

 

 

1) 상향식(Bottom-up) 방법

- 위에서 설명한 순서대로 가장 작은 부분 문제부터 풀어 저장해놓고 나중에 참조하는 방법이다.

- 모든 배열의 인덱스는 1부터 ~ n+1까지 사용 //0은 0원이니까

 

using System.IO;
using System;

class Program
{
    static void Main()
    {
        //막대 길이 입력
         int n = int.Parse(Console.ReadLine());
         int[] price = new int[n+1];
         
        //길이 만큼 가격 입력
        for(int i=1; i<=n; i++){
            price[i] = int.Parse(Console.ReadLine());
        }
        
        //각 길이별 최대 가격 저장할 배열
        int[] maxPrice = new int[n+1];
        
        //길이 1부터 최대 가격 계산
        for(int i=1; i<=n; i++){
            int max = 0;
            for(int j=1; j<=i; j++){
                max = Math.Max(max, price[j] + maxPrice[i-j]);
            }
            
            maxPrice[i] = max;
        }
        
        Console.WriteLine(maxPrice[n]);
    }
}

 

2) 메모하기를 이용한 하향식 재귀 방법

- 일반적인 하향식 재귀 풀이에서 배열을 하나 더 추가해, 재계산을 피하도록 함

using System.IO;
using System;

class Program
{
    static void Main()
    {
        //막대 길이 입력
         int n = int.Parse(Console.ReadLine());
         int[] price = new int[n+1];
         int[] maxPrice = new int[n+1];
         
        //길이 만큼 가격 입력
        for(int i=1; i<=n; i++){
            price[i] = int.Parse(Console.ReadLine());
        }
        
        Console.WriteLine(cutRod(price,n,maxPrice));
    }
    
    
    public static int cutRod(int[] price, int n, int[] maxPrice){
        if(n==0){
            return 0;
        }
        
        if(maxPrice[n]!=0){
            return maxPrice[n];
        }
        
        int max = int.MinValue;
        for(int i=1; i<=n; i++){
            max = Math.Max(max, price[i] + cutRod(price, n-i, maxPrice));
        }
        
        maxPrice[n] = max;
        return max;
    }
}