[Softeer]택배 마스터 광우 파이썬 풀이

택배 마스터 광우¶

문제 page: https://softeer.ai/practice/info.do?eventIdx=1&psProblemId=581&sw_prbl_sbms_sn=64051

알고리즘 유형: 완전탐색

문제를 보자마자 떠올렸을 알고리즘은 다음과 같으실 것입니다.

if now_weight + next_weight > M:
    work += 1

if work >= K:
    min_work = min(min_work, sum(weights))

print(min_work)

중요한 건 위의 알고리즘의 경우 모든 리스트를 섞는 경우의 수(순열)에 대해서 작동해야 합니다.
근데 그렇게 하면 됩니다.(?)

In [ ]:

from itertools import permutations
import math
N, M, K = [int(x) for x in input().split()]
array =[int(x) for x in input().split()]

min_work = math.inf
for sample in list(permutations(array)):
    now = 0
    weight = []
    work = 0
    while work < K:
        for e in sample:
            if work >= K:
                break
            if now + e > M:
                work += 1
                weight.append(now)
                now = e
            else:
                now += e
    if min_work > sum(weight):
        min_work = sum(weight)

print(min_work)