[5강 재귀] 3번 상담 문제 질문드립니다.

안녕하세요, 강의 너무 잘 듣고 있습니다.

5강 최적화 강의의 3번 상담이라는 문제를 푸는데, 제공해주신 답변과 제가 작성한 코드에 차이가 있어 질문드립니다.

[모범답안]

def recur(idx, result):
    global answer

    

    if idx > n:
        if idx > n+1: return
        answer = max(answer, result)
        return

    recur(idx + table[idx][0], result + table[idx][1])
    recur(idx + 1, result)


n = int(input())
table = [[] for _ in range(n+1)]
for i in range(n):
    a, b = map(int, input().split())
    table[i+1] = [a, b]

# print(table)

answer = 0

recur(1, 0)

print(answer)

[제가 작성한 코드]

# 14501
import sys
sys.stdin =  open('/Desktop/dev/BackJoon/5강_최적화/3_상담.txt','r')

input = sys.stdin.readline
N = int(input())
arr = [list(map(int, input().split())) for _ in range(N)]

def recur(idx, price):
    global ans
    
    if idx >= N: # 배열의 마지막 인덱스를 지나가는 것은 무시
        return 
    if idx == N-1: # 배열의 마지막 인덱스
        ans = max(ans, price)    
        return
    
    recur(idx+arr[idx][0], price+arr[idx][1])
    recur(idx+1, price)

ans = 0
recur(0,0)
print(ans)

모범답안과 종료조건이 다른 것을 확인했습니다.

제가 생각했을 때, 배열의 마지막 인덱스 (N-1)에서도 하루 짜리 일을 할 수도 있기 때문에 recur를 한번 더 돌수 있고 그 다음 인덱스 N 시점에서 종료되어야 한다고 생각해서 코드를 작성했습니다.

혹시 제가 잘못 생각하고 있는 부분이 있을까요?

또한, 제공해주신 답변은

table을 N+1의 길이로 생성
recur(1,0)로 시작

하고 있는데 해당 문제는 꼭 이렇게 접근해야 되는 것인가요?

미리 감사드립니다.

아뇨! 완벽하게 이해하신 것 같습니다 ㅎㅎ

지금 출근길이라 모바일 환경에서 답변을 드리는데

제가 강의에서 코드를 1부터 시작하는 이유는 1일차 2일차.. 로 언급되는 백준문제여서 쉬운 설명을 위해서 한거고,

당연히 인덱스는 0부터 계산하셔도 됩니다!

또한, 조건문을 바꿔서 계산해보려고 하시는 시도도 훌륭합니다 🙂

그런데, 제 조건문과 결과가 완전히 다르게 나올 것 같은데 반례도 확인하셨나요?

제 조건문은 ( 인덱스의 끝에 도달할때까지 나오는 모든 경우의 수의 정답을 비교한다. )

이지만 , 혜경님이 작성해주신 조건문은 ( 인덱스 마지막에서 계산되는 경우위 수의 정답을 비교한다. )

입니다.

이 부분에 대해서 한번 고민해 보시고, 오답이 될지 없다는 확신이 있으시면 조건문을 혜경님이 방식으로 써주면 됩니다.

하지만 제가 처음에 말씀드린 완전탐색적 사고방식으로는,

리소스( 시간과 메모리 )가 충분하다면 고민할 필요없이 컴퓨터에게 모든 경우의 수를 비교시키는게 더 쉬운 방법이라거 생각합니다 🙂

좋은 질문이네요! 감사합니다!

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