[SWEA] 5215 햄버거 다이어트 (Python) - Backtracking

📌 풀이

Code

def backtrack(idx, score_sum, cal_sum):
    global max_score
    if cal_sum > L:                     # 경로 중간에 이미 제한 칼로리 넘어버리면 그 경로 가망 없음
        return                          # 가지치기
    
    if idx == N:                        # 최대 인덱스 도달 시
        if score_sum > max_score:       # 현재 점수 합이 기존 최대 점수보다 높으면
            max_score = score_sum       # 최대값 갱신
    else:                               # 아직 최대 인덱스 도달 못했으면
        # 현재 재료를 선택하는 경우
        backtrack(idx + 1, score_sum + score_lst[idx], cal_sum + cal_lst[idx])
        # 현재 재료를 선택하지 않는 경우
        backtrack(idx + 1, score_sum, cal_sum)


for tc in range(1, int(input())+1):
    N, L = map(int, input().split())    # N: 재료의 수, L: 제한 칼로리
    max_score = 0                       # 최대 점수

    score_lst = []
    cal_lst = []
    for _ in range(N):
        score, cal = map(int, input().split())      # 점수, 칼로리 받기
        score_lst.append(score)
        cal_lst.append(cal)
    
    backtrack(0, 0, 0)
    
    print(f'#{tc}', max_score)

---

Solution

1. 재료의 수와 제한 칼로리 입력 받기
 
2. 각 재료의 점수, 칼로리를 입력 받고 점수 리스트와 칼로리 리스트에 차례로 append
 
3. 현재 재료의 인덱스, 현재까지의 점수 합, 칼로리 합을 인자로 갖는 backtrack 함수 실행
 
4. 인덱스가 최대에 도달할 때까지 인덱스를 1씩 올리면서 재귀 호출

• 재귀 호출 시 현재 재료를 포함하는 경로와 미포함하는 경로 두 가지 경로를 각각 호출

5. 재귀 경로 도중 재료 칼로리 합이 이미 제한 칼로리를 넘어버리면 그 경로는 가망이 없으므로 가지치기
 
6. 최대 인덱스에 도달했으면, 현재까지의 재료 점수 합과 최대 점수를 비교하여 최대 점수 갱신

---

깨달은 점

저는 처음에 문제를 보고 '조합을 만들어야겠구나' 생각이 들자마자 습관적으로 방문리스트를 만들었습니다.
그런데 풀다보니 이 문제는 방문리스트가 필요 없더군요..?
 
DFS와 방문리스트는 무조건 같이 간다는 고정관념 때문에 발생한 일이지요 ㅠㅠ

앞으로는 습관을 경계하고, 코딩에 들어가기 전에 먼저 꼼꼼하게 논리를 설계하자.