[Python, 파이썬] SWEA 5215. 햄버거 다이어트

햄버거 재료에 대한 점수와 가게에서 제공하는 재료에 대한 칼로리가 주어졌을 때,
정해진 칼로리 이하 조합 중에서 점수가 가장 높은 햄버거를 가하는 문제.

 

 

def BFS(i, taste, hambegur):

    global max_score # 최대 칼로리

    if(hambegur > L): # 최대 칼로리를 넘으면
        return

    if taste > max_score: # 점수가 더 높은 맛 찾았을 시
        max_score = taste 

    if(i==N): # 재료 모두 사용
        return

    BFS(i+1, taste+score[i], hambegur+calorie[i]) # 현재 재료 선택
    BFS(i+1, taste, hambegur) # 현재 재료 미선택   
    

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

for test_case in range(1, T+1):

    N, L = map(int, input().split()) # 재료의 수 N, 제한 칼로리 L

    score = [] # 재료의 점수
    calorie = [] # 각 칼로리
    max_score = 0 # 맛에 대한 점수가 높은 햄버거의 점수

    # 재료의 점수, 칼로리 입력받기
    for _ in range(N):
        s, c = map(int, input().split())
        score.append(s) 
        calorie.append(c)

    BFS(0, 0, 0)
    print("#%d %d" %(test_case, max_score))

 

 

 

 

[문제풀이]

---

DP를 이용해서도 풀 수 있다고는 하나 BFS+백트래킹을 사용하면 아주 쉽게 풀 수 있는 문제.

 

각 재료마다 선택, 미선택으로 BFS 돌리면 끝난다.

BFS(i+1, taste+score[i], hambegur+calorie[i]) # 현재 재료 선택
BFS(i+1, taste, hambegur) # 현재 재료 미선택   

 

이러면 모든 경우의 수를 확인 할 수 있는데, 이때 재료가 끝나거나 최대 칼로리를 넘으면 그대로 종료.

저장한 최대 점수를 넘으면 저장!