• 카테고리

    질문 & 답변
  • 세부 분야

    알고리즘 · 자료구조

  • 해결 여부

    해결됨

[탑다운] 상담문제

24.04.29 11:48 작성 조회수 48

1

if day > N:
    return -999999999999

해당 부분을 -2 혹은 -99 등으로 조건을 바꾸면 왜 통과가 안되는지 궁금합니다. -999까지는 통과가 되더라고요

 

import sys

N = int(sys.stdin.readline())
answer = 0
plan = []
for _ in range(N):
    plan.append(list(map(int, sys.stdin.readline().split())))

#dp[day]를 계산하는 함수 
def rec(day):
  if day > N:
    return -999999999999
  if day == N:
    return 0

  #dp[day]가 한번이라도 계산된적 있다면 두번 할 필요없음
  if dp[day] != -1:
    return dp[day]

  dp[day] = max(rec(day + plan[day][0]) + plan[day][1], rec(day + 1))
  return dp[day]


dp = [-1 for _ in range(N + 1)]
rec(0)
print(dp[0]) #dp[0]은 첫째날 선택했는지 아닌지까지 포함한 최대값 

답변 1

답변을 작성해보세요.

0

-9999999 를 해주는 이유는 해당 날짜를 지난 경우입니다. 따라서 정답이 될 수 없는 경우입니다.

 

이 문제에서 dp에 저장하는 값은 max값이기 때문에 -999999를 해주는 것으로 아주 작은 수로 만들어서, 해당 날짜를 지난 경우를 정답에서 제외 하고 있습니다.

 

백준에서

-99에서 통과가 안되지만 -999는 통과가 되는 이유는 백준의 예제가

 

  • 정답이 될 수 없는 경우 중에서 가장 큰 수

  • 정답이 될 수 있는 경우 중에서 가장 큰 수

     

     

     

     

 

이 두 수의 차이가 99이상, 999이하이기 때문에 발생하는 현상입니다 🙂

보시고도 이해가 안되시면 답글 남겨주세요!

nayeon Kim님의 프로필

nayeon Kim

질문자

2024.05.11

아하 넵 이해했습니다 감사합니다~