2차원 DP 1번 문제

질문 감사합니다!

문제를 설명해주실 때,

처음에 recur으로 접근하신 후 dp로 바꿔서 설명을 해주셨는데요,

15:45 부분에서 설명해주신 내용 중

return으로 인해 계산이 끝나지 않고 이웃 칸으로 이동해서 계속해서 계산을 이어가도록 하는 부분이

return 0 을 return dp[y][x] 로 바꾸는 부분에 해당하는 것인지 질문드립니다.

네, 맞습니다! 진행하는 공간까지의 모든 경우의 수를 확인해서 최적의 값을 DP에 저장하고, 그 DP 값을 바탕으로 그 다음 값을 계산함으로써 현재까지 최적의 경우의 수를 바탕으로 계산을 이어갈 수 있습니다 ㅎㅎ

또한, 마지막에 답을 출력할 때,

print(max(map(max,dp))+1

왜 +1을 해주는지 궁금합니다.

제가 만든 계산식은 몇 번을 이동했는가 를 계산하고 있는데, 문제에서는 몇 칸을 이동했는지를 묻고 있기 때문에 +1이 됩니다! ( 시작점을 포함해야해서 그렇습니다 🙂 )

안녕하세요, 인프런 AI 인턴입니다.
질문하신 내용에 대해 답변 드리겠습니다.

첫 번째 질문에 대한 답변입니다.
return 0을 return dp[y][x]로 바꾸는 이유는 이미 계산된 dp의 값을 재사용하기 위함입니다. 이는 동적 계획법(Dynamic Programming)의 기본 개념 중 하나인 메모이제이션(memoization)을 활용한 것으로, 한 번 계산된 결과를 저장해두었다가 같은 계산을 반복하지 않도록 하여 프로그램의 효율성을 높이는 방법입니다.

두 번째 질문에 대한 답변입니다.
print(max(map(max, dp)) + 1 에서 +1을 해주는 것은, dp 테이블이 0부터 채워지기 시작하여 실제 최댓값을 구할 때는 +1을 해줘야 정확한 결과를 얻을 수 있기 때문입니다. 쉽게 말해, 문제의 조건이나 구현 방식에 따라 배열의 인덱스는 0부터 시작하지만, 실제 문제에서 요구하는 계산 결과는 1부터 카운트될 수 있으므로 구한 결과에 +1을 해주어야 최종 해답이 됩니다.

정답 코드가 포함된 이미지가 검은색으로 보이는데, 해당 이미지에 오류가 있을 수 있으므로 실제 정답 코드를 확인하시려면 강의 제공자 또는 인프런 고객 지원을 통해 접촉하시는 것을 권장합니다.

추가적인 질문이나 궁금한 점이 있으시다면 언제든지 문의하시기 바랍니다.
오늘도 즐거운 학습 시간 되세요~