CuttingRod.cs

using System;

namespace CSharpPractice
{
    class Program
    {
        static void Main(string[] args)
        {
            /*
            https://www.geeksforgeeks.org/cutting-a-rod-dp-13/

            Dynamic Programming 문제.
            재귀 + memoize 로 풀었으며, 기존 문제는 통나무 제한 길이가 제시된 배열 길이로 제한된다.
            하지만 내 경우 통나무 제한 길이를 memo 배열 길이 - 1까지 해 보았다.

            통나무 길이에 따라 다음과 같이 시장 가격이 매겨졌을 경우 우리가 가지고 있는 통나무를 어떻게 쪼개서 팔아야 최대 수익을 낼 수 있는지 알아내자. 
            Given a rod of length n inches and an array of prices that contains prices of all pieces of size smaller than n. 
            Determine the maximum value obtainable by cutting up the rod and selling the pieces.

            lenth   길이 i    1   2   3   4   5   6   7   8
            price   가격 pi   1   5   8   9   10  17  17  20

            */
            int[] pricePerRodLength = new int[9]
            {
                0,1,5,8,9,10,17,17,20
            };

            int[] memo = new int[1001];

            int mostExpensivePrice = CalculateMostExpensivePrice(ref pricePerRodLength, ref memo, 1000);
            Console.WriteLine("\n" + mostExpensivePrice);
        }

        private static int CalculateMostExpensivePrice(ref int[] pricePerRodLength, ref int[] memo, int rodLength)
        {
            if(rodLength < memo.Length && memo[rodLength] > 0)
            {
                return memo[rodLength];
            }

            if(rodLength > pricePerRodLength.Length-1)
            {
                return memo[rodLength] = CalculateMostExpensivePrice(ref pricePerRodLength, ref memo, pricePerRodLength.Length-1) + 
                    CalculateMostExpensivePrice(ref pricePerRodLength, ref memo, rodLength - (pricePerRodLength.Length-1));
            }

            if(rodLength <= 1)
            {
                return memo[rodLength] = pricePerRodLength[1];
            }
            else if(rodLength == 2)
            {
                return memo[rodLength] = Math.Max(pricePerRodLength[2], pricePerRodLength[1] + pricePerRodLength[1]);
            }
            else if(rodLength == 3)
            {
                return memo[rodLength] = Math.Max(pricePerRodLength[3], 
                    Math.Max(pricePerRodLength[2] + pricePerRodLength[1], 
                    pricePerRodLength[1] + pricePerRodLength[1] + pricePerRodLength[1]));
            }

            int mostExpensivePrice = 0;
            for (int i = rodLength-1; i >= 1; i--)
            {
                mostExpensivePrice = Math.Max(mostExpensivePrice, 
                    Math.Max(pricePerRodLength[rodLength], 
                        CalculateMostExpensivePrice(ref pricePerRodLength, ref memo, i) +
                        CalculateMostExpensivePrice(ref pricePerRodLength, ref memo, rodLength-i)));
            }
            memo[rodLength] = mostExpensivePrice;
            return mostExpensivePrice;
        }
    }
}