[Softeer][level3] 택배 마스터 광우 - 파이썬(Python)

 

https://softeer.ai/practice/info.do?idx=1&eid=581 

Softeer

 

문제

여름 휴가를 떠나기 위해 용돈이 필요했던 광우는 H택배 상하차 아르바이트를 지원 했다. 광우는 평소에 운동을 하지않아 힘쓰는 데에 자신이 없었지만, 머리 하나 만큼은 비상해 택배가 내려오는 레일의 순서를 조작해서 최소한의 무게만 들 수 있게 일을 하려고 한다.

레일은 N개이며, 각각의 레일은 Ni 무게 전용 레일로 주어진다. (같은 무게의 레일은 주어지지 않는다.) 레일의 순서가 정해지면 택배 바구니 무게(M)를 넘어가기 전까지 택배 바구니에 택배를 담아 들고 옮겨야 한다. 레일 순서대로 택배를 담되, 바구니 무게를 초과하지 않은 만큼 담아서 이동하게 되면 1번 일한 것으로 쳐준다. (단, 택배는 순서대로 담아야 하므로 레일의 순서를 건너 뛰어 담을 수는 없다)

총 K번 일을 하는데 최소한의 무게로 일을 할 수 있게 광우를 도와주는 프로그램을 만들어 보자.

 

 

 

 

레일의 개수가 5개이고 택배 바구니의 무게를 20, 일을 시행해야 하는 횟수를 4번 이라고 했을 때, 레일의 순서가 | 5 | 8 | 10 | 19 | 7 | 이 된다면 총 4번 수행 했을 때 답은 62가 된다. 

 

1번 (5+8)

2번 (5+8) + (10)

3번 (5+8) + (10) + (19)

4번 (5+8) + (10) + (19) + (7+5+8) = 62

 

하지만 최적의 순서는 | 5 | 10 | 8 | 19 | 7 | 이 된다.

 

1번 (5+10)

2번 (5+10) + (8)

3번 (5+10) + (8) + (19)

4번 (5+10) + (8) + (19) + (7+5) = 54

 

 

 

---

 

💡 사고과정

1️⃣ 레일의 순서 정하기

 순서가 중요하기 떄문에 permutations를 사용해서 순열을 만든다.

 

2️⃣ 레일의 순서가 정해졌을 때 

 - 작업의 횟수가 정해져있으므로 작업의 횟수만큼 반복

 - 버킷에 채울수있으면 버킷에 넣고, 해당 값을 리스트 뒤에 다시 넣어준다. 

 - 인덱스를 증가시킨다. (다음레일 확인 위함)

 

- 만약 버킷에 채울 수 없으면, 현재 레일을 사용했을 떄 총 무게를 계산하기 위해 버킷에 있는걸 thisall에 더해주고,

버킷무게는 초기화한다. 

이때 한번의 작업을 한것이므로 work를 1증가시킨다. 

 

3️⃣ 해당 레일에서 최종적으로 나온 this_all 무게에 대해
최종적으로 최소무게인지 확인해준다. 

 

 

 

💻 내가 쓴 정답코드

from itertools import permutations
import sys
input = sys.stdin.readline 

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

rails_info = permutations(input_rails, n)

result = sys.maxsize

for now_rails in rails_info:

    rails = list(now_rails)

    i = 0
    bucket = 0
    work = 0
    this_all = 0
    
    while work != k: # 작업의 수만큼만 반복
        if bucket + rails[i] <= m:  #m: 바구니 무게
            bucket += rails[i]
            rails.append(rails[i])
            i+=1
        else: 
            this_all += bucket
            bucket = 0
            work += 1
            
    result = min(result, this_all)

print(result)