SWEA - 햄버거 다이어트(5215)

접근방식

문제를 읽어보면 조합을 사용해서 풀어야한다는 것을 알 수 있음

import itertools from combinations 를 통해 조합 라이브러리를 임포트함

재료의 수와 제한 칼로리를 cnt, limit_kcal 변수로 받아주고

맛에 대한 점수와 칼로리는 data라는 변수에 할당해줌

max_score를 0으로 선언

재료의 수 만큼 for문을 돌면서 내부에서 for문을 한 번 더 돔

for value in combinations(data, j) -> j의 범위를 1부터 cnt+1까지 했으므로 cnt가 5이면 j는 1,2,3,4,5가 되고 위의 for문을 통해 1개를 뽑을 때, 2개를 뽑을 때, ... 5개를 뽑을 때를 각각 구함

value는 data를 받아오는데, value[][0]은 점수, value[][1]은 칼로리이므로 score, kcal을 각각 0으로 선언해주고 value의 길이만큼(몇 개를 뽑는지) score, kcal에 각각 점수와 칼로리를 더해줌

그리고 kcal이 limit_kcal보다 크게되면 더 이상 진행할 수 없으므로 continue를 사용하고 현재 score가 max_score보다 크면 max_score를 score로 할당해줌

코드

from itertools import combinations

T = int(input())
for i in range(1, T+1):
 cnt, limit_kcal = map(int, input().split())
 
 data = [list(map(int, input().split())) for _ in range(cnt)]
 
 max_score = 0
 for j in range(1, cnt+1):
 for value in combinations(data, j):
 score = 0
 kcal = 0
 for k in range(len(value)):
 kcal += value[k][1]
 score += value[k][0]
 if kcal > limit_kcal:
 continue
 if max_score < score:
 max_score = score
 
 print('#'+str(i), max_score)