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

※ SW Expert 아카데미의 문제를 무단 복제하는 것을 금지합니다.

출처:

SW Expert Academy

나의 풀이 (시간초과)

def dfs(cnt,sk):
    global ans
    ans=max(ans,sk[0])
    if cnt==N:
        return
    for i in range(N):
        if not visited[i] and sk_list[i][1]+sk[1]<=L:
            visited[i]=True
            dfs(cnt+1,[sk[0]+sk_list[i][0],sk[1]+sk_list[i][1]])
            visited[i]=False
           
T = int(input())

for test_case in range(1, T + 1):
    N,L=map(int,input().strip().split())
    ans=0
    sk_list=[]
    for _ in range(N):
        sk_list.append(list(map(int,input().strip().split())))
    visited=[False]*N
    dfs(0,[0,0])
    print(f'#{test_case} {ans}')

• 위 코드는 dfs로 풀기 위해 작성한 코드이다. 중복된 재료를 사용하면 안되기 때문에 visited로 사용 여부를 기록했다.
• 그런데 생각해보니, 첫번째에 1번 재료를 고르던, 마지막에 1번 재료를 고르던 동일하다.
• 즉 같은 재료의 조합을 갖는 경우의 수가 매우 많이 나올 수 있다.
• 이 때문에 시간초과가 발생했다.

나의 풀이

def dfs(cnt,sk):
    global ans
    if sk[1]>L:
        return
    ans=max(ans,sk[0])
    if cnt==N:
        return
    dfs(cnt+1,sk)
    dfs(cnt+1,[sk[0]+sk_list[cnt][0],sk[1]+sk_list[cnt][1]])
            

T = int(input())

for test_case in range(1, T + 1):
    N,L=map(int,input().strip().split())
    ans=0
    sk_list=[]
    for _ in range(N):
        sk_list.append(list(map(int,input().strip().split())))
    dfs(0,[0,0])
    print(f'#{test_case} {ans}')

• 개선한 코드는 위와 같다.
• visited로 하지 않고, 1번 재료를 고를지 안고를지, 그다음은 2번 재료를 고를지 안고를지 이렇게 순차적으로 선택하도록 하여, 제한된 칼로리를 넘어가면 return을 하고, 안넘어간다면 max()를 통해 정답을 유지하도록 코드를 작성하였다.