Softeer level3 택배 마스터 광우 Python

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

Softeer

import sys
input = sys.stdin.readline
N, M, K = map(int, input().split())
rails = list(map(int, input().split()))
minW = 10e9

def dfs(S, V, box):
    if S == N:
        global minW
        nowW = basket(box)
        if nowW < minW:
            minW = nowW
        return
    for i in range(N):
        if i not in V:
            dfs(S+1, V+[i], box+[rails[i]])

def basket(box):
    tmp = 0
    idx = 0
    for _ in range(K):
        nowW = 0
        while True:
            if nowW + box[idx] > M:
                tmp += nowW
                break
            nowW += box[idx]
            idx = (idx+1)%N
    return tmp
dfs(0, [], [])
print(minW)

다들 itertools의 permutations를 써서 푸시는 것 같은데 나는 그냥 dfs돌렸다.

백준의 n과 m(시리즈 13?까지 있을 정도로 초급자에게 악명높은 문제임)을 많이 풀어봤다면 이정도는 껌이다.
만약 n과 m에 대해서 감이 1도 안 잡힌다면 유투브 IT편의점 문어박사님을 검색해서 공부하길 바랍니다.

솔직히 중간에 가지치기 하면 백트래킹도 될 수 있는데 사람은 단순하게 살라고 시간초과 나는 거 아니면 이대로 두는 것도 나쁘지 않다고 생각한다.