[SWEA/D3] 5215 햄버거 다이어트 / 백트래킹

문제 바로가기

SW Expert Academy

나의 코드 및 설명 - 이진트리

• dfs함수를 정의하고 재료를 선택할 때와 선택하지 않고 그냥 넘어갈 때의 두 가지 경우를 하위 함수를 호출하는 방식으로 구현하였다.

def dfs(count, score_sum, cal_sum):
    global max_score
    if cal_sum>limit: #처음에 limit 대신 1000을 넣어서 TC 20개 중 10개만 맞음 ..
        return
    if max_score < score_sum:
        max_score = score_sum
    if count == n:
        return
    dfs(count+1, score_sum+score_list[count], cal_sum+cal_list[count])    #선택o
    dfs(count+1, score_sum, cal_sum)    #선택x

t = int(input())

for test_case in range(1, t+1):
    n, limit = map(int, input().split())
    score_list = []
    cal_list = []
    max_score = 0
    for _ in range(n):
        score, cal = map(int, input().split())
        score_list.append(score)
        cal_list.append(cal)
    dfs(0, 0, 0)
    print("#{} {}".format(test_case, max_score))

나의 코드 및 설명 - 멀티트리(시간초과로 풀이에 실패했다.. ㅠ)

• 멀티 트리로 꼭 풀어보고 싶어서 여러번 도전했는데도 풀이에 실패했다... ㅠ 자꾸 TC 20개 중 10개만 맞고 시간초과가 뜬다... 이유가 무엇인지 모르겠다 ... ㅠ 종료 조건도 잘 작성했고, 방문 처리도 확실하게 했는데 왜그럴까 ..
• 아래의 두 번째의 코드로 Pass 판정 받았다!

def dfs(count, temp_sum, cal_sum):
    global max_score
    if sum(cal_sum) > limit:
        return
    if max_score < sum(temp_sum):
        max_score = sum(temp_sum)
    if count >= n:
        return
    for i in range(n):
        if visited[i] == 0:
            visited[i] = 1
            temp_sum.append(score_list[i])
            cal_sum.append(cal_list[i])
            dfs(count+1, temp_sum, cal_sum)
            visited[i] = 0
            temp_sum.pop()
            cal_sum.pop()

t = int(input())

for test_case in range(1, t+1):
    n, limit = map(int, input().split())
    score_list = []
    cal_list = []
    temp_sum = []
    cal_sum = []
    max_score = 0
    visited = [0]*n
    for _ in range(n):
        score, cal = map(int, input().split())
        score_list.append(score)
        cal_list.append(cal)
    dfs(0, [0], [0])
    print("#{} {}".format(test_case, max_score))

def dfs(count, start, score_sum, cal_sum):
    global max_score
    if cal_sum > l:
        return
    if max_score < score_sum:
        max_score = score_sum
    if count == n:
        return
    for i in range(start, n):
        dfs(count+1, i+1, score_sum+score_list[i], cal_sum+cal_list[i])

t = int(input())
for test_case in range(1,t+1):
    n, l = map(int, input().split())
    score_list = []
    cal_list = []
    for _ in range(n):
        score, cal = map(int, input().split())
        score_list.append(score)
        cal_list.append(cal)

    max_score = 0
    dfs(0,0,0,0)
    print("#{} {}".format(test_case, max_score))

피드백

본래 이 문제는 멀티트리 백트래킹 방식으로 풀어보았는데 자꾸 TC 20개 중 10개만 맞았다고 fail이 떴다... 그래서 다른 백트래킹 기본 문제부터 다시 풀었다. 백준 '단계별 풀어보기' 에서 백트래킹 문제를 풀고, 리턴하는 부분이 이해가 잘 되지 않아 동영상 강의도 듣고.. 그렇게 공부한 결과 이진트리 방식을 통해서는 Pass 판정을 받을 수 있었다. 그런데 멀티트리 방식으로는 시간초과로 인해 또 다시 fail이 떴다. 이유를 찾지 못했다. ㅠ 하루동안 고민했던 문제이고 그래서 꼭 멀티트리 방식으로 풀고 싶었는데 못풀었다. >> 다시 풀어본 결과 Pass를 받았다! 그래도 이 문제 덕분에 백트래킹에 대해 조금이나마 더 익숙해질 수 있어서 나름 의미있는 문제였다.