16.11 다이빙 보드

문제

다량의 널빤지를 이어 붙여서 다이빙 보드를 만들려고 한다. 널빤지는 길이가 긴 것과 짧은 것 두가지 종류가 있는데 정확히 K개의 널빤지를 사용하여 다이빙 보드를 만들어야 한다. 가능한 다이빙 보드의 길이를 모두 구하는 메서드를 작성하라

 

해결법

1. 재귀적 해법

재귀적으로 K번의 널빤지를 선택하면 다이빙 보드를 완성할 수 있고 완성된 보드를 리스트에 추가하면 된다. 

+ 메모이제이션 

def getAllLengths(k, long, short):
    memo = set()
    lengths = set()

def allLengths(k, lengths , total, long, short, memo):
    if k == 0:
        lengths.add(total)
    key = (total, k)
    if key in memo :
        return
    allLengths(k-1, lengths, total+long, long, short, memo)
    allLengths(k-1, lengths, total-short, long, short, memo)
    memo.add(key)
    return

 

2. 수열의 합만을 구하기

 어쩌피 널빤지는 2가지종류밖에 없으니 나올수 있는 경우의 수는 K+1밖에 없다.

K = 7이면 long이 0개일때 shourt는 7, long이 1개일때 shourt는 6, ... 이런식으로

그러면 그냥 loop를 이용해서 구할 수 있다. 

 하지만 한가지 생각해야할 부분이 있다. 두 판자의 길이가 같은 경우를 생각해야한다 

그런경우에는 원소가 하나인 배열을 반환하면 된다!!

def getAllLengths(k, long, short):

    lengths = []
    cnt_s = k
    if long != short:
        while cnt_s >=0 :
            cnt_l = k - cnt_s
            length = long*cnt_l + short*cnt_s
            lengths.add(length)
            cnt_s -=1
    else :
        return [long*k]
    return lengths