[SWEA/Python] SW Expert Academy 5215번 - 햄버거 다이어트

SW Expert Academy #5215 햄버거 다이어트

SW Expert Academy

def calc(i, now_kal, now_taste, max_taste):
    for k in range(i+1, n):
        max_taste = calc(k, now_kal + kal[k], now_taste + taste[k], max_taste)
    if now_kal <= l:
        max_taste = max(max_taste, now_taste)
    return max_taste

t = int(input())   # 테스트 케이스 수

for tk in range(t):
    n, l = map(int, input().split())   # n: 재료 수, l: 제한 칼로리
    taste, kal = [], []
    best = 0
    for i in range(n):
        t, k = map(int, input().split())
        taste.append(t)
        kal.append(k)
    for i in range(n):
        best = max(best, calc(i, kal[i], taste[i], 0))
    print(f'#{tk + 1} {best}')

완전 탐색 방법

 

 

실패한 그리디 방식 풀이

t = int(input())   # 테스트 케이스 수

for tk in range(t):
    n, l = map(int, input().split())   # n: 재료 수, l: 제한 칼로리
    taste, kal = [], []
    cal = []
    for i in range(n):
        t, k = map(int, input().split())
        taste.append(t)
        kal.append(k)
        cal.append((t/k, i, k))
    cal.sort(key=lambda x: (x[0], -x[2]))
    now_taste, now_kal = 0, 0
    for i in range(n-1, -1, -1):
        x = cal[i][1]
        if kal[x] + now_kal <= l:
            now_kal += kal[x]
            now_taste += taste[x]
    print(f'#{tk+1} {now_taste}')

문제 보자마자 그리디 문제구나 했는데 ,, 아니네 ㅎㅎ;

 

---

 

맨날 까먹어서 정리하는 key lambda 사용해서 정렬하기

cal.sort(key=lambda x: (x[0], -x[2]))
# 첫 번째 인자 기준으로 오름차순 정렬 후, 똑같은 값 세 번째 인자 기준으로 내림차순 정렬