DP 기본문제인 막대기 자르기(백준에 없는문제)

코드&그림매칭

자식들간 비교를 하여 그 중 최대값을 반환하는 코드

1. 막대기 자르기

문제의 일반화
나누어지는 대상이 1차이로 나누어지고 각각의 값(길이)에 대한 가치 부여되는 문제라면 재귀의 기저사례로부터 올라오면서 차례차례 구할 수 있다. 

좀더 일반화
나누어지는 대상이 n차이로 나누어지고 각각의 값(길이)에 대한 가치가 부여되는 문제라면 재귀의 기저사례로부터 올라오면서 차례차례 구할수 있다.

 

Bottom-up 방식으로 해결: 반복문을 사용하여 값을 1부터 시작하여 1일때의 최대 가치, 2일 때의 최대가치를 차근차근 구하여 이전에 얻은 값을 다음에 얻을 값을 계산할때 이용한다. 값이 가장 작을 때 그 값을 구성할수 있는 경우는 오직 한가지 뿐임을 이용한것. 예를들어 숫자 50을 쪼개는 방법은 여러가지다. 하지만 숫자 1을 구성할수 있는 방법은 한가지 뿐이 없다. (기저가치?라고 부르고 싶음).

Top-down방식의 재귀를 이용한 해결책: 해결의 중요 실마리는 기저사례로 길이가 1인 막대기의에서 얻을 수 있는 최대가치가 정해져 있다는 것을 인지하는 것과 이것을 통해 길이가 2인 막대기에서 얻을 수 있는 최대가치를 얻을 수 있다는 것을 인지하는 것이다.

(Pi=정해져있는 막대기 길이에 대한 가치 배열, Mi=아직 정해져 있지 않은 길이가 i인 막대기에서 얻을 수 있는 최대가치로 기저 사례부터 올라오면서 작은길이의 막대기부터 정의된다)

길이가1=>(1,0) P1은 정해져 있으므로 이로부터 M1이 정해짐.

길이가2=>(1,1)P1이 정해져있고M1도 위로부터 알게되었으니 이 값과 (2,0)(P2는 이미 나와있는 값)을 비교해서 큰값이 M2가 정해짐.

.

.

.

.

.길이가n인 막대기를 어떻게 나누었을 때 최댓값인지를 알수 있음!

 

사실 문제의 해결책을 정리하면서 느끼는 거지만 이 문제의 키 포인트는 길이가n인 막대기를 어떻게 나누어야 최대값을 얻는지는 기저사례부터 올라오면서 얻은 결과값들(M[1], M[2], M[3], ... , M[n-1])에 이미 길이가 n인 막대기를 나누는 모든 경우에 대한 값이 있음을 인지하고 이를 활용하는 것이다. 즉 길이가 1인 막대기의 최대가치를 알면 길이가 2인 막대기의 최대가치를 알수 있고 2인 막대기의 최대가치를 알면 길이가 3인 막대기의 최대가치도 알수 있게 된다.

즉, 문제해결의 사고 순서를 문제에서 묻는 "길이가 n인 막대기를 어떻게 나누어야 최대가치를 가질까?"에서 >> "길이를 나누는 방법을 차근차근 모든 경우의 수로 순차적으로 나누어서  생각해보자 예를들면 (1, n-1),(2, n-2), ... , (n,0) 물론 이 와중에 n-k 를 나누는 방식이 또 무수하게 나뉘는 문제상황이 있어 사고의 흐름을 흐트릴수 있겠지만 재귀라는 훌륭한 무기로 이를 모두 규칙에 맞추어 정갈하게 해치울수 있다" >>"재귀의 밑바닥을 찍고 오면서 M[1], M[2], M[3]를 순차적으로 구할수 있고 재귀트리의 정상부분에서는 위에서 언급한 길이가 N인 막대기를 나누는 모든 경우에 대한 최대가치들 M[1], M[2], M[3], ... , M[n-1]을 알수 있다(사실 이것을 생각하는게 쉽게 않네...)"

 

막대기 자르기 문제와 피보나치 수열 문제의 공통점: 두 문제 모두 불변인 기저사례가 있다. 막대기의 길이가 1일 때의 고정된 값이 있고(물론 길이가 1인 막대기의 고정값은 막대기를 더이상 잘게 나눌수 없고 길이가 1인 막대기의 가치는 하나의 값으로 정해져 있기 때문에 고정된값이라고 한거임) 피보나치 수열의 첫번째와 두번째 항은 1, 1 이라는 변하지 않는 기저사례가 있고 그로부터 출발한다.

 

막대기 자르기 문제와 피보나치 수열 문제의 차이점: 막대기 자르기 문제 같은 경우 5라는 길이의 막대를 자르는 방법은 한가지만 있는 것이 아니다. 하지만 피보나치 수열은 5번째 항은 고정된 값을가진 3번째항과 4번째항의 합으로 그 값이 고정되어 있다. 이러한 차이점 때문에 피보나치 수열은 Top-down이 가능하지만 막대기 문제는 Top-down이 가능하지 않을 것이다. 오직 Bottom-up방식만 가능할 것이다! ==>> 틀렸다!! 길이가 5인 막대를 자르는 방법을 반복문을 통해 모두 체크하는 것이다... 이 정도로 할줄은 상상도 못했다 사실...

아... 아니네 막대기 자르기도 Top-down이 가능하구나...ㅠㅜ

알고리즘 해답 코드를 작성하는데 있어 무었보다 해당코드가 그림으로 어떻게 구성되는지를 그릴수 있는 것이고 그 그림이 너무 복잡하여 말로 표현하는게 그닥 도움이 되지않는 재귀같은 경우는 그림에서 코드로 바로 대칭을 시킬수 있도록 공부하는게 해답이다. 하여 그림이 어떤 순서로 그려지는 지를 아래 사진으로 첨부한다.

 

 

 

막대기 자르기

문제: 하나의 막대기가 있다. 막대기 길이에 따라 가격이 다르다. 최고의 수익을 얻도록 막대기를 자르라.

길이(i) 0 1 2 3 4 5 6 7 8 9 10
가격(Pi) 0 1 5 8 9 10 17 17 20 24 30

예를 들면 길이가 4인 막대기를 자를 때 얻을 수 있는 최대 가격은, 길이를 2인 막대기 두 개로 나누어서 가격을 5 + 5 = 10으로 만드는 겁니다. 길이가 6인 막대는 자르지 않고 그냥 팔았을 때 최대 17의 가격을 얻을 수 있습니다.

이 문제는 그냥 풀기엔 좀 복잡하게 보이지만 동적 프로그래밍을 사용하면 간단하게 풀 수 있습니다.

길이가 n인 막대기의 최대 가격을 Rn이라고 했을 때, Rn = max(Pi + Rn-i) (i는 1부터 n)로 나타낼 수 있습니다. max는 여러 값 중의 최대값을 의미합니다. 예를 들면 아까 길이가 4인 막대기의 최대 가격은 R4 = max(P1 + R3, P2 + R2, P3 + R1, P4 + R0)이죠.

P1, P2, P3은 이미 주어져 있습니다. 이제 R1, R2, R3을 구해야 하는데요.
R1은 Rn = max(Pi + Rn-i) (i는 1부터 n) 식에서 max(P1 + R0)이므로 1입니다.
R2는 max(P1 + R1, P2 + R0)이라 max(2, 5) = 5입니다.
R3는 max(P1 + R2, P2 + R1, P3 + R0)라서 max(6, 6, 8) = 8입니다.
R4는 위의 값들로부터 max(9, 10, 9, 9) = 10임을 알 수 있습니다.

위의 과정에서 R1, R2, R3는 계속해서 나옵니다. 이 값들을 저장해 두고 재사용하면 일일히 재계산하지 않아도 되죠. 바로 여기서 Top-down으로 불리는 메모이제이션을 사용할 수도 있고, Bottom-up이라 불리는 상향식 계산법을 사용할 수도 있습니다.

상향식 계산법이 성능이 더 좋은 경우가 많으므로 상향식 계산법을 사용하겠습니다.

r이 바로 이전에 계산한 값들을 저장하는 부분입니다. 안의 반복문은 r[1]부터 r[j]를 구하는 부분입니다. 내부반복문중에서 마지막으로 계산된 q는 각 길이에 대한 최대 가격을 의미하고요. 바깥의 반복문은 안의 반복문으로부터 구했던 r[1]~r[j]를 활용해 Rn의 최대값을 도출하고 있습니다.

 

p=[0, 1, 5, 8, 9, 10, 17, 17, 20, 24, 30]
def cuttingStick(p,n):#Bottom-up Tabulation방식 
    m=[0]*(n+1)#답을 가지고 있는 배열 m. m[j]는 j길이의 막대기를 나누는 방법중 최대비용
    #점화식R(n)=max(P(i)+R(n-i))
    for j in range(1, n+1):
        q=-1#있을수 없는 막대기의 길이
        for i in range(1, j+1):
            q=max(q,p[i]+m[j-i])
        m[j]=q
    return m[n]
print(cuttingStick(p, 2))#5
print(cuttingStick(p, 3))#8
print(cuttingStick(p, 4))#10
print(cuttingStick(p, 7))#18

m=[-1]*(40)
def cuttingStickTd(p,n,m):#Top-down Memoization방식
    if(m[n]>=0):
        return m[n]
    if n==0:
        q=0
    else:
        q=-1
        for i in range(1, n+1):
            q=max(q, p[i]+cuttingStickTd(p, n-i, m))
    m[n]=q
    return q

print(cuttingStickTd(p, 2, m))
m=[-1]*(40)
print(cuttingStickTd(p, 3, m))
m=[-1]*(40)
print(cuttingStickTd(p, 4, m))
m=[-1]*(40)
print(cuttingStickTd(p, 7, m))

 

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;

public class Main{
    //이 2중 for문의 주목할 점은 항상 구할려는 것(answer[i])바로 이전 한끝 까지의 모든 정보를 이용하여 구하려는 것을
    //구한다는 것이다.
    public static int cutRod(int[]p, int n) {
        int[]answer=new int[p.length];
        for(int i=1;i<=n;i++){
            int q=-1;
            for(int j=1;j<=i;j++){
                q=Math.max(q, p[j]+answer[i-j]);
            }
            answer[i]=q;
        }
    return answer[n];
    }

    public static void main(String[] args) throws IOException {
        BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
        int n=Integer.parseInt(br.readLine());
        int[] p = {0, 1, 5, 8, 9, 10, 17, 17, 20, 24, 30};
        System.out.println(cutRod(p,n));

    }
}

출처: 내머리+https://doorbw.tistory.com/28+ https://www.zerocho.com/category/Algorithm/post/584b979a580277001862f182