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

https://softeer.ai/practice/info.do?eventIdx=1&psProblemId=581 

Softeer

from itertools import permutations
import sys
n, m, k = map(int,sys.stdin.readline().split())
rail = list(map(int,sys.stdin.readline().split()))

rail_list = list(permutations(rail, n))


def weight(m, k, array):
    basket = 0
    count = 0
    order = 0
    answer = 0
    while True:
        # 배열에 있는 짐을 실어 넣는다.
        basket += array[order]
        # while 문이 돌면서 바구니에 m 보다 무게가 낮다면
        if basket < m:
            # 만약에 한바퀴 다 돌았으면 앞순서로 보내고
            if order == len(array)-1:
                order = 0
            # 안돌았으면 순서를 증가 시켜준다.
            else:
                order +=1
        # 무게가 같으면
        elif basket == m:
            count +=1
            answer += basket
            basket =0
            if order == len(array)-1:
                order = 0
            # 안돌았으면 순서를 증가 시켜준다.
            else:
                order +=1
        # 무게가 넘었으면
        else:
            basket -= array[order]
            count += 1
            answer += basket
            basket = 0

        if count == k:
            break
    return answer
answer_list = []
for i in range(len(rail_list)):
    a = weight(m, k, rail_list[i])
    answer_list.append(a)
answer = min(answer_list)
print(answer)

"""
5 20 4
5 8 10 19 7
"""

문제를 풀면서 무슨 점화식이 있나? 뭐 다른 방법이 있나? 하면서 엄청 고민했다.

근데 딱히 떠오르지 않았고 결국에는 구글링을 하며 블로그 하나를 참고 했다.

 

https://autumnrain.tistory.com/entry/%ED%83%9D%EB%B0%B0-%EB%A7%88%EC%8A%A4%ED%84%B0-%EA%B4%91%EC%9A%B0

택배 마스터 광우

 

이 블로그에서 이문제는 부르드포스로 해결해야하고 모든 경우를 다 고려해서 문제를 풀어야 한다고 했다.

부르드포스알고리즘은 쉽게 말하면 무식하게 모든 경우를 다 찾아보고 고려하는 것이다.

 

문제 풀이 조건

1. 순열을 이용해 나올수 있는 모든 배열을 찾아낸다.

2. 그 배열에서 조건에 맞추어서 바구니에 넣어보면 조건에 만족하는 지 고려하며 해당 배열의 무게를 정답의 후보가 될수 있는 리스트에 저장한다.

3. 최종적으로 모든 경우를 고려한후 무게가 제일 낮은 것을 뽑아내면 끝이다.

 

문제를 다풀고 특정 경우를  

# 무게가 같으면
        elif basket == m:
            count +=1
            answer += basket
            basket =0
            if order == len(array)-1:
                order = 0
            # 안돌았으면 순서를 증가 시켜준다.
            else:
                order +=1

 

이부분에서 순서를 하나 증가 시키거나 0으로 만드는 경우를 고려하지 않고 그냥 넘어가 많은 시간을 잡아먹었다.

꼭 문제 풀때 모든 경우를 체크하고 확인해야겠다.