[파이썬] 소프티어 택배 마스터 광우

문제 확인

Softeer

• 사이트에서 문제를 확인해주세요.

나의 풀이

레일의 개수가 10 이하기 때문에 가능한 모든 레일 조합을 순열로 구한 뒤 완전 탐색으로 풀었다. 

import sys
from itertools import permutations

n, m, k = map(int, input().split())
rail_info = list(map(int, input().split()))
# N이 작기 때문에 모든 경우의 수 확인
cases = list(permutations(rail_info, n))

min_sum = 1e9
# 완전 탐색
for case in cases:
    # 각 탐색마다 k 횟수만큼 시행
    case_sum = 0
    idx = 0
    for i in range(k):
        temp_sum = 0
        while True:
            temp_sum += case[idx % n]
            # 바구니 무게 초과
            if temp_sum > m:
                temp_sum -= case[idx % n]
                # 최소 무게 저장
                case_sum += temp_sum
                break
            else:
                idx += 1
    min_sum = min(min_sum, case_sum)

print(min_sum)