햄버거 다이어트

import sys
sys.stdin = open("input.txt", "r")

from itertools import combinations as cb
T = int(input())

for test_case in range(1, T + 1):
    N, totalCal = map(int, input().split())
    answer, tempList = 0, []

    for i in range(N):
        score, cal = map(int, input().split())
        tempList.append([score, cal])

    # 모든 가능한 조합 탐색 (2^21 -> 완전탐색 가능)
    for repeat in range(1, N+1):
        combCal = [sum(t[1] for t in x) for x in cb(tempList, repeat)]
        combScore = [sum(t[0] for t in x) for x in cb(tempList, repeat)]

        for idx, item in enumerate(combCal):
            if item <= totalCal:
                answer = max(answer, combScore[idx])

    print("#" + str(test_case) + " " + str(answer))

우선 모든 가능한 경우를 조합으로 나타내도 타임 아웃이 걸리지 않는다는 것을 파악하면 매우 쉬운 문제이다. (D3)

다만 score, cal를 하나의 자료구조로 넣고 그 안에서 조합을 돌려 특정 부분에서만 합(sum)을 구하는 로직을 잘 기억해두자.

combCal = [sum(t[1] for t in x) for x in cb(tempList, repeat)]
이런 식으로 조합을 돌린 구조에 item에서의 t(한번 더 참조) 가 들어가면 해결할 수 있다.

문제 출처: https://swexpertacademy.com/main/code/problem/problemDetail.do?problemLevel=3&contestProbId=AWT-lPB6dHUDFAVT&categoryId=AWT-lPB6dHUDFAVT&categoryType=CODE&problemTitle=&orderBy=SUBMIT_COUNT&selectCodeLang=ALL&select-1=3&pageSize=10&pageIndex=1