inflearn logo
강의

강의

N
챌린지

챌린지

멘토링

멘토링

N
클립

클립

로드맵

로드맵

지식공유

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

[탑다운] 상담문제

해결된 질문

202

nayeon Kim

작성한 질문수 2

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]은 첫째날 선택했는지 아닌지까지 포함한 최대값 

python 코딩-테스트 알고리즘

답변 1

0

코딩 센세

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

 

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

 

백준에서

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

 

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

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

     

     

     

     

 

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

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

0

nayeon Kim

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

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