재귀 경우의수 14501 퇴사문제

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

녜힁

작성한 질문수

2주만에 통과하는 알고리즘 코딩테스트 (2024년)

해결된 질문

작성

300

수정됨

def recur(idx,money):
    global answer

    if idx == n:
        answer = max(answer, money)
        return
    if idx > n:
        return
    
    # idx 해당날에 상담 ㄱㄱ
    recur(idx + arr[idx][0], money + arr[idx][1])

    # pass 하는날
    recur(idx + 1, money)

n = int(input())
arr = [[] for _ in range(n+1)]
for i in range(n):
    t,p = map(int,input().split())
    arr[i+1] = [t,p]

answer = -999999    
recur(1,0)
print(answer)

위는 제 코드입니다. 이 코드를 백준에 제출하면 오답이 나옵니다. 테스트 케이스의 경우에는 맞았는데.
근데 위 코드에서 if에 해당하는 부분을 아래와 같이 고치면 정답이 나오더라고요.

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

제가 아직 재귀에 대한 완벽한 이해가 없고, 어떤 식으로 재귀함수가 동작하는 지는 정확히 몰라서 구글링을 통해 재귀 함수는 스택방식으로 작용한다라는 내용도 공부해보고 왜 n+1은 통과고 n은 실패인지 암만 생각해봐도 모르겠네요,,

도와주십시오!!

python 코딩-테스트 알고리즘

답변 1

코딩 센세

지식공유자

재귀에 대한 이해가 부족 하신건 아닌 것 같고, 단순히 idx를 조금 착각해서 생긴 문제 같습니다.

for i in range(n):
    t,p = map(int,input().split())
    arr[i+1] = [t,p]

입력을 받으실 때 1번부터 채우셨고,

만약 1일차부터 7일차까지 상담을 할 수 있다고 하면 퇴사날짜는 8일 이겠죠?

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

그렇기 때문에 아래 수정하신 코드처럼 8일차가 되면 코드가 종료되도록 하면 문제 없이 동작합니다.

if idx == n:
        answer = max(answer, money)
        return
    if idx > n:
        return

수정 전의 코드를 그대로 사용하고 싶으시다면, 그렇다면 입력을 idx 0번부터 채우면 수정이 되겠죠?

for i in range(n):
    t,p = map(int,input().split())
    arr[i] = [t,p]

recur(0,0)

이렇게 수정해주시면 정상적으로 동작합니다 :)

혹시라도 이해가 어려우시면 답글 남겨주세요! 추가 설명과 예제 달아드리겠습니다!

녜힁

작성한 질문수

전체 Q&A

질문하기