DFS 문제풀이 UVA301 수송업 피이썬 존나 구린 해답

짜고보니 복잡도가 큰... 프로그램을 짰구나 싶지만
일단 짰으니 올림 ㅠㅠ
나는 자야함
내일 일찍 혐생 가아햠

http://book.interpark.com/product/BookDisplay.do?_method=detail&sc.shopNo=0000400000&sc.prdNo=201620016&sc.saNo=003002001&bid1=search&bid2=product&bid3=title&bid4=001

이 책의 '수송업' 문제를 푼 것

아아 ACM 문제구먼
https://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&problem=237

난 그냥 인풋 을 좀 바꿔서 풀었음
귀찮아서
근데 ACM문제였구나
앞으론 안바꾸고 걍 풀어봐야지...

<>

10 5 4
3 5 10
2 4 9
0 2 5
2 5 8

<>


def read_file(file_name):
    result = []
    with open(file_name, 'r') as f:
        lines = f.readlines()
        for l in lines:
            result.append(tuple(int(e) for e in l.split()))
    return result

tups = read_file("input_trainstation")

max_people, n_st, n_jm = tups[0]
joomoons = [t for t in tups[1:n_jm+1]] #인풋형태 내맘대루 바꿈 ㅎㅎmax_money = 0
def calc_money(check_list):
    total_m = 0    for j,c in zip(joomoons, check_list):
        f,t,p=j
        total_m+= c*((t-f)*p)
    return total_m

def is_possible(check_list):
    for st in range(n_st):
        total_p = 0        for j_idx, c in enumerate(check_list):
            f, t, p = joomoons[j_idx]
            if f<=st and st                total_p+=p*c
        if total_p > max_people:
            return False    return True
def DFS(check_list):
    global max_money
    if len(check_list) is n_jm:
        money = calc_money(check_list)
        if money > max_money:
            max_money = money
        return
    if is_possible(check_list+[1]):
        DFS(check_list+[1])
    DFS(check_list+[0])

DFS([])
print(max_money)