JZ67 밧줄 자르기 - 귀속, 동적 기획

제목 설명

길이가 n인 밧줄을 하나 드릴게요. 밧줄을 정수 길이의 m단(m, n 모두 정수, n>1 및 m>1)으로 자르세요. 각 밧줄의 길이는 k[0], k[1],..., k[m]로 적어 주세요.실례지만 k[0]xk[1]x...xk[m] 가능한 최대 곱셈은 얼마입니까?예를 들어 밧줄의 길이가 8이면 우리는 그것을 길이가 각각 2, 3, 3의 세 단락으로 자르는데 이때 얻은 최대 곱셈은 18이다.

풀다

1. 귀속
분석: f(n)f(n)f(n)가 우리가 필요로 하는 길이가 n인 커팅 m단의 최대 곱셈을 정의합니다.각 단락에 대해 말하자면 자르지 않는 것을 선택할 수 있다. 즉, f(n)f(n)f(n)를 선택할 수도 있고, 자르는 것을 선택할 수도 있다. 자르는 것은 f(i)∗f(n−i)(i=1,., n/2)f(i)*f(n-i)(i=1,..., n/2)f(i)∗f(n−i)(i=1,..., n/2), ===>로 나눌 수 있기 때문에 귀속 공식을 얻을 수 있다. ∗f(n−i)}f(n)=max\{f(n), f(i)*f(n-i)\}f(n)=max{f(n), f(i)∗f(n−i)}.코드:

function cutRope(number)
{
    if(number < 4){
        return number - 1
    }
    return cutRopeMain(number)
   
}
function cutRopeMain(n){
    if(n < 5){
        return n
    }
    let max = 0
    for(let i = 1; i < (n/2) + 1; i++){
        max = Math.max(cutRopeMain(i)*cutRopeMain(n - i), max)
    }
    return max
}

2. 동적 계획
분석: 상술한 반복적인 사상도 동적 기획의 코드 코드로 쓸 수 있다.

function cutRope(number)
{
    if(number == 2){
        return 1
    }
    if(number == 3){
        return 2
    }
    let dp = []  // 
    dp[1] = 1  // 
    dp[2] = 2
    dp[3] = 3
    for(let i = 4; i <= number; i++){
        dp[i] = 0  // 
        for(let j = 1; j <= i/2; j++){
           dp[i] = Math.max(dp[j]*dp[i-j], dp[i])
        }
    }
    return dp[number]
}

3. 수학 공식법
분석: 밧줄의 길이는 n이고 m분으로 나눈다. 그러면 먼저 매 분의 길이를 x로 설정하고 분수 m=n/x를 설정하면 결과는 n/x개의 x상승 f(x)=x^(n/x) 구도이다. 아래 그림과 같이 문제는 n/3의 개수 위로 돌아간다.

n이 3으로 정리될 때 곱하기 = 3^(n/3);

.n을 3여1로 나누었을 때 이때 1이 하나 더 생겼다는 것을 발견했다. 이 1은 계륵이 아니냐. 그러나 앞의 3을 꺼내서 이 1과 앞의 3을 2와 2로 분해하면 커진다. 그래서 곱셈은 3^(n/3-1)*4이다

n을 3여 2로 나눌 때 곱셈은 3^(n/3)*2이다

코드:

function cutRope(number)
{
    if(number == 2) return 1
    if(number == 3) return 2
    let m = number % 3, n = Math.floor(number / 3)
    switch(m){
        case 0:return Math.pow(3, n);
        case 1:return Math.pow(3, n - 1)*4;
        case 2:return Math.pow(3, n)*2;
    }
}