[소프티어 6273번] 택배 마스터 광우

Softeer - 현대자동차그룹 SW인재확보플랫폼

 

import sys
from itertools import permutations

input = sys.stdin.readline

# 레일의 순서를 조작해서 최소한의 무게만 들 수 있게 일을 함
# N개의 레일, 각 레일은 Ni 무게 전용 레일로 주어진다.(같은 무게의 레일 X)

# 레일의 순서가 정해지면 택배 바구니 무게(M)를 넘어가기 전까지 택배 바구니에 택배를 담아 들고 옮겨야 함
# 레일 순서대로 택배를 담되, 바구니 무게를 초과하지 않은 만큼 담아서 이동하게 되면 1번 일한 것으로 쳐줌
# (단, 택배는 순서대로 담아야 하므로 레일의 순서를 건너 뛸 순 없다)

# 총 k번 일을 하는데 최소한의 무게로 일을 할 수 있도록 하자

n, m, k = map(int,input().split())

weights = list(map(int,input().split()))

cases = list(permutations(weights))

answer = float("inf")

def get_work(weight_list):

    current_weight = 0
    temp_k = 0
    i = -1
    work = 0

    while True:

        if current_weight + weight_list[(i+1)%n] > m:
            temp_k += 1
            current_weight = weight_list[(i+1)%n]
            if temp_k >= k:
                break
        else:
            current_weight += weight_list[(i+1)%n]
        
        work += weight_list[(i+1)%n]

        if i == (n-1):
            i = 0
        else:
            i += 1
    return work

for case in cases:
    result = get_work(case)
    if result < answer:
        answer = result

print(answer)

 

이번 문제는 택배의 무게(Ni)가 정해져있는 레일 N개의 순서를 조작해서, K번 일을 할 때 들 수 있는 최소 무게를 구하는 문제이다.(레일의 순서가 정해지면 순서대로 바구니에 담되, 바구니 무게를 초과해서는 안된다)

 

처음에 이 문제를 접했을 때는 정렬이나 DP를 사용해서 풀이할 수 있을 줄 알았는데, 특별한 규칙이 보이지않아 Permutations를 활용한 완전탐색으로 풀이하기로 결심했다.(N이 최대 10이기 때문에 N! 이라도 시간초과가 발생하지 않음)

 

따라서 레일의 순서를 조작할 수 있는 모든 경우의 수를 구한 뒤, 주어진 레일에 대하여 총 K번 일했을 때 들게 되는 무게의 양을 구하는 함수(get_work)를 구현하여 풀이하였다.