[백준] 18429 근손실 (실버3) / 백트래킹

문제요약

나의 코드 및 설명 01 (변수로 넘겨줄 시)

#변수로 넘겨줄 시
def dfs(count, muscle):
    global ans
    #중량이 500이하 되면 리턴
    if muscle < 500:
        return
    #키트를 다 선택했다면 ans +=1
    if count == n:
        ans+=1
        return

    for i in range(len(kit)):
        #중복된 키트를 사용하지 않기 위해 방문 처리
        if visited[i] == 0:
            visited[i] = 1
            #키트 사용 시 중량을 같이 넘겨준다.
            dfs(count+1, muscle+kit[i]-k)
            #돌아와서는 방문처리 해제
            visited[i] = 0

n,k = map(int, input().split())
kit = list(map(int, input().split()))
visited = [0] * n
ans = 0

dfs(0, 500)
print(ans)

나의 코드 및 설명 02 (외부에 리스트 둘 시)

def dfs(count):
    global ans
    if sum(muscle_list) < 500:
        return
    if count == n:
        ans+=1
        return

    for i in range(len(kit)):
        if visited[i] == 0:
            visited[i] = 1
            muscle_list.append(kit[i])
            muscle_list.append(-k)
            dfs(count+1)
            visited[i] = 0
            muscle_list.pop()
            muscle_list.pop()


n,k = map(int, input().split())
kit = list(map(int, input().split()))
visited = [0] * n
muscle_list = [500]
ans = 0

dfs(0)
print(ans)

피드백

백트래킹 연습을 위해 풀어본 문제. 그동안 백트래킹 문제를 풀며 리턴 시 동작 과정에 대해 이해하기 쉽지 않았는데 이번 문제를 통해 조금은 더 이해할 수 있었던 것 같다. 변수에 값을 저장해서 하위 함수 호출 시 넘겨줌으로써 나중에 리턴할 때 그 값이 이전의 값으로 돌아오게 된다. 때문에 변수에 저장된 값을 다시 되돌리는 추가 작업을 별도로 해주지 않아도 된다.