[탑다운] 상담문제
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이하이기 때문에 발생하는 현상입니다 🙂
보시고도 이해가 안되시면 답글 남겨주세요!
dp[x]가 최대값이라고 확신할수 있는 이유
0
46
1
1090번 문제 질문
0
151
1
유니온파인드
0
112
1
투포인터 25:15 질문
1
129
1
#1090번 문제 반례가 궁금합니다.
0
148
1
예제코드 자바입니다
1
187
1
정수론 파트 #2247 문제에 대한 질문입니다!
0
102
0
코드 오류
0
186
1
2강 정수론 문제3 #1407 질문
0
127
0
이차원 배열 (int형)dp로 0 혹은 -1로 체크하는 방법 말고 boolean형 배열로 체크해서 바로 리턴해줄 수 없나요?
0
154
0
1717번 최적화
0
112
0
백준 22988 문제 질문
1
193
2
[Python] 백준 1090번 문제
1
226
3
강의자료에서
1
162
2
2503 문제 제한 조건 질문!
1
249
2
백준 22988 번 문제
1
193
1
추가 강의 순서
1
181
2
(*문제 풀이)1090 테스트케이스 1번 C++
1
221
2
7강 RGB 색칠하기 질문 있습니다.
1
161
2
정수론 약수 빠르게 구하기 질문
1
257
1
1090 문제의 2, 3번째 아이디어는 결국 같은거 아닌가요?
1
375
2
1090 문제 관련하여 맨해튼 거리 최솟값에 대해 질문 있습니다.
1
223
2
누적합 문제 3번 질문
1
216
2
기억 ( 누적합 ) 강의 11660 문제
1
163
2





