[SWEA] 5215 햄버거 다이어트 (파이썬/python) - 백트래킹, combinations

🎈문제

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&&&&&&&&&&

🎁알고리즘 및 접근

경우의 수

1. itertools를 사용하는 방법과 백트래킹을 사용하는 방법이 있다.

2. 중복 x, 순서 상관 x 이므로 itertools의 combinations를 사용해보자.

3. 백트래킹으로 안해보면 아쉬우니까 백트래킹 코드도 소개한다.

💻 combinations를 사용한 코드

# swea 햄버거 다이어트 - combinations활용

from itertools import combinations
T = int(input())
for test_case in range(1,T+1):
    n, l = map(int,input().split())
    hamburger = []
    for _ in range(n):
        t,k = map(int,input().split())  # 점수, 칼로리
        hamburger.append([t,k])
    count_answer = 0
    for i in range(1,n+1):
        for j in combinations(hamburger,i):
            cnt_kal = 0
            cnt_tast = 0
            for m in j:
                cnt_kal += m[1]
                cnt_tast += m[0]
            if cnt_kal <= l:
                count_answer = max(cnt_tast,count_answer)

    print(f"#{test_case} {count_answer}")

💻 백트래킹을 사용한 코드

# swea 5215 햄버거 다이어트 - 백트래킹 활용

def check(num,hamburger):
    cnt_score = 0
    cnt_kal = 0
    for i in range(num):
        cnt_score += hamburger[i][0]
        cnt_kal += hamburger[i][1]
    if cnt_kal <= l:
        return cnt_score
    return 0

def dfs(num,depth):
    global answer
    if num == len(hamburger):
        answer = max(answer, check(num,hamburger))
        return

    for i in range(depth,n):
        hamburger.append(ingredients[i])
        dfs(num,i+1)
        hamburger.pop()
    return

T = int(input())
for test_case in range(1,T+1):
    n, l = map(int,input().split())

    # 햄버거 재료 입력 받기
    ingredients = []
    for _ in range(n):
        t,k = map(int,input().split())  # 점수, 칼로리
        ingredients.append([t,k])

    answer = 0
    hamburger = []
    for num in range(1,n+1):
        dfs(num,0)

    print(f"#{test_case} {answer}")

 

🎄코드 설명

쉬워서 코드에 대한 설명은 생략한다.

백트래킹으로 꼭 풀어보자.

백트래킹 코드가 어렵다면 백준 백트래킹 문제를 꼭 모두 풀어보고 넘어가자.