[ SW Expert Academy ] 5215. 햄버거 다이어트

아.. 간만에 시간초과..

짜릿하네 ^^ 

 

1차 제출 [ 10 / 20 ] FAIL , 17분

 

def dfs(array, score, total_calory, depth):
    global result
    if depth == n :
        return
    result = max(result, score)
    for i in range(n):
        if not visited[i] and total_calory + array[i][1] < limit:
            visited[i] = True
            dfs(array, score + array[i][0], total_calory+array[i][1], depth+1)
            visited[i] = False

T = int(input())
for tc in range(1, T+1):
    n, limit = map(int, input().split()) # 재료수, 제한칼로리
    ingredient = []
    result = 0
    visited = [False for _ in range(n)]
    for i in range(n):
        t, k = map(int, input().split()) # 점수, 칼로리
        ingredient.append((t, k))
    dfs(ingredient, 0, 0, 1)

    print("#{} {}".format(tc, result))

 

 

아 ,, 왜 틀렸지..  눈물 나.. 

 

2차 제출. PASS

def dfs(array, score, total_calory, now):
    global result
    if total_calory > limit:
        return
    if result < score:
        result = score
    if now == n:
        return
    dfs(array, score + array[now][0], total_calory+array[now][1], now+1)
    dfs(array, score, total_calory, now+1)

T = int(input())
for tc in range(1, T+1):
    n, limit = map(int, input().split()) # 재료수, 제한칼로리
    ingredient = []
    result = 0
    visited = [False for _ in range(n)]
    for i in range(n):
        t, k = map(int, input().split()) # 점수, 칼로리
        ingredient.append((t, k))
    dfs(ingredient, 0, 0, 0)

    print("#{} {}".format(tc, result))