문제설명
John and Mary want to travel between a few towns A, B, C ... Mary has on a sheet of paper a list of distances between these towns. ls = [50, 55, 57, 58, 60]. John is tired of driving and he says to Mary that he doesn't want to drive more than t = 174 miles and he will visit only 3 towns.
Which distances, hence which towns, they will choose so that the sum of the distances is the biggest possible to please Mary and John?
문제요약 : 파라미터 t(한계거리), k(여행지 개수), ls(여행지까지 거리 리스트)가 주어짐.
여행지를 k개를 골라서 그 합이 t보다 같거나 작은 합계중에 t(한계거리)에 가까운 합계를 구하는 함수 choose_best_sum을 구현하시오. 만약 조건에 맞는 합계가 하나도 없으면 None을 return하시오.
(해석을 제가 좀 이상하게 했는데 예시 참조하시면 이해가 더 쉬울겁니다.)
제한사항
None
입출력 예시
ts = [50, 55, 56, 57, 58] choose_best_sum(163, 3, ts) -> 163
ys = [91, 74, 73, 85, 73, 81, 87] choose_best_sum(230, 3, ys) -> 228
xs = [100, 76, 56, 44, 89, 73, 68, 56, 64, 123, 2333, 144, 50, 132, 123, 34, 89] choose_best_sum(430, 8, xs) -> None풀이
import itertools
def choose_best_sum(t, k, ls):
possible_num_box = [sum(v) for v in (itertools.combinations(ls, k)) if sum(v) <= t]
return max(possible_num_box) if possible_num_box else None경우의 수를 구할 때 매우 유용한 모듈인 itertools를 사용했습니다.
itertool의 combination함수를 사용해서 리스트 중 k개를 선택할 때 나올 수 있는 모든 조합의 경우의 수를 구합니다. 그 중에 리스트컴프리헨션을 사용해 t보다 같거나 작은 합계가 담긴 리스트를 구합니다.
삼항연산자를 활용해 만약 리스트가 없으면([]) None 존재하면 max를 사용해 최대값을 return해주면 됩니다.
다른풀이
def tribonacci(signature, n):
return max((s for s in (sum(dists) for dists in combinations(ls, k)) if s <= t), default=None)거의 똑같지만 삼항연산자 없이 default를 사용해 한 줄로 처리했습니다.
