[SWEA - D3] 5215. 햄버거 다이어트

 

 

나의 코드 

def DFS(L,score,kcal):
    global res 
    if kcal > k:
        return
    if score > res:
        res = score 
    if L == n:
        return
        
    s,c = arr[L]
    DFS(L+1,score+s, kcal+c)
    DFS(L+1,score,kcal)
    
T = int(input())
for t in range(1,T+1):
    n,k = map(int,input().split()) 
    arr = []
    res = 0
    for _ in range(n):
        a,b = map(int,input().split()) 
        arr.append((a,b))
    DFS(0,0,0)
    print("#"+str(t) , res )

 

DFS 를 이용한 풀이 

 

햄버거 재료수(n), 넘지 말아야 하는 칼로리수(k)을 입력받고

리스트를 생성하고 맛과 칼로리를 저장한 후 

 

칼로리가 넘어가면 탐색을 수행X

기존에 저장된 최대 맛보다 크면 갱신 

리스트를 다돌면 return

 

재료를 썼을 때, 안 썼을 때 를 각각 탐색