[완전탐색] 소프티어 (lv3. 택배 마스터 광우)

문제

제약조건

입력 & 출력

해설

이 문제는 가능한 모든 경우를 다 탐색하여 최솟값을 정답으로 출력하는 완전탐색 문제 유형이다.

1. permutations로 가능한 모든 정렬을 다 구한다.
2. k번 박스 상자를 옮기면서 가능한 무게를 다 더한 다음에 각 정렬마다 ans를 갱신해준다.

리스트를 queue처럼 사용해서 문제를 해결할 수 있었다.

정답 코드

import sys
import itertools
input = sys.stdin.readline
n, m, k = map(int, input().split())    # 레일 개수, 택배 바구니 무게, 일의 시행 횟수
pack = list(map(int, input().split()))
p = list(itertools.permutations(pack, n))
ans = 1000000
for queue in p:
    temp_ans = 0
    po = 0
    que = list(queue)
    for i in range(k):
        temp = 0
        while temp <= m:
            a = que.pop(0)
            que.append(a)
            temp += a
            if temp + que[0] > m:
                break
        po += temp
    temp_ans += po
    ans = min(ans, temp_ans)
print(ans)