[leetcode] 줄 자르기.

동적 기획

def cut(n):
    if n < 2:
        return 0
    elif n == 2:
        return 1
    elif n == 3:
        return 2
    else:
        lst = [0, 1, 2, 3]
        for i in range(4, n+1):
            max = 0
            for j in range(1, i//2+1):
                tmp = lst[j] * lst[i-j]
                max = tmp if tmp > max else max
            lst.append(max)
        return lst[-1]

욕심 계산법

def cut(n):
    if n < 2:
        return 0
    elif n == 2:
        return 1
    elif n == 3:
        return 2
    else:
        if n % 3 == 0:
            return 3 ** (n // 3)
        elif n % 3 == 1:
            return 3 ** (n // 3 - 1) * 4
        else:
            return 3 ** (n // 3) * 2

테스트 용례

assert cut(8) == 18