5강 재귀(경우의 수) 4번 문제 질문드립니다.

안녕하세요, 선생님의 강의를 잘 듣고 있는 1인 입니다.

1) 강의를 듣고 4번 문제를 아래와 같이 풀었는데요, 정답이 왜 0이 나오는건지, 어느 부분이 잘못된 건지 모르겠어서 질문드립니다.

(5강에서 적으실때 line 18의 idx에 1을 더해주지 않으셨는데 이 부분은 +1을 빠트린게 맞으신거죠?)

2)또한, 어떤 경우에 global answer를 써주는지도 한번 다루어주셨으면 좋겠습니다.
3) line 8의 weight > B가 아닌 weight >= B가 되는게 더 맞는게 아닌지 질문드립니다. weight == B인 경우에 한 번 더 반복문을 돌면 이미 초과된 가방에 새로운 물건의 value를 추가해서 더하게 되는 것처럼 보이는데요, 혹시 제가 잘못 생각하고 있을까요?

import sys

sys.setrecursionlimit(99999999)

def recur(idx,weight,value):
    global answer

    if weight > B:
        return
    if idx == N:
        answer = max(answer,value)
        return
    
    recur(idx+1, weight + items[idx][0],value + items[idx][1])
    recur(idx+1,weight,value)


N,B = map(int,input().split())

items = [list(map(int,input().split())) for _ in range(N)]

answer = 0
recur(0,0,0)

print(answer)

수정해서 정답이 나오는 코드입니다.

#1. 5강에서 적으실때 line 18의 idx에 1을 더해주지 않으셨는데 이 부분은 +1을 빠트린게 맞으신거죠?

넵, 강의는 수정될 예정이고 아래 설명란에 언급되어 있습니다!

#2. 또한, 어떤 경우에 global answer를 써주는지도 한번 다루어주셨으면 좋겠습니다.

def 으로 만든 함수 속에서는 함수 외부에서 선언된 값을 변경시키는 것이 불가능합니다!

함수 밖에서 asnwer = 0으로 선언한 값을 변경하기 위해서는 함수 속에서 밖에 있는 변수값을 변경 시킬 권한을 줘야 하는데 그 때, global을 사용하면 외부 변수 값을 변환시킬 권한을 줄 수 있습니다 :)

#3. line 8의 weight > B가 아닌 weight >= B가 되는게 더 맞는게 아닌지 질문드립니다. weight == B인 경우에 한 번 더 반복문을 돌면 이미 초과된 가방에 새로운 물건의 value를 추가해서 더하게 되는 것처럼 보이는데요, 혹시 제가 잘못 생각하고 있을까요?

이 질문의 반례가 문제의 예제여서, 이 부분은 한번 더 고민해보시고 답글을 달아주세요! ( 문제를 풀기 위해 필요한 고민입니다! )

이 예제가 바로 반례입니다!

#4. 정답이 왜 0이 나오는건지, 어느 부분이 잘못된 건지 모르겠어서 질문드립니다.

[ 보여주신 코드의 가장 큰 문제점은 answer 값을 변경하는 부분이 없습니다! ]

answer = 0 으로 선언한뒤에 answer를 건드리지 않고 그대로 print를 하고 있기 때문에 정답이 0으로 나오는 것 입니다!

return을 사용하고 싶으셨다면 아래와 같이

answer = recur(0,0,0)

return된 값으로 정답을 바꾸어 주는 방향으로 여러 줄을 수정 해야 하는데, 재귀를 통해 경우의 수에 대한 이해를 하는 과정이기 때문에 굳이 지금 return을 이용해서 정답을 바꾸려고 하지 않으셔도 다음 강의에서 return을 이용하게 됩니다 :)

그래서 global을 이용해서 answer 변수의 변경 권한을 주고, 정답을 max 비교를 통해서 바꿔주면서 경우의 수를 탐색하면 정답이 나옵니다!

한번 더 도전해보시고 또 질문 남겨주세요! 감사합니다!

인프런 커뮤니티 질문&답변