2차원 DP 1번 문제

Question

안녕하세요, 추가강의를 듣다가 2가지 질문사항이 생겨 다시 글을 쓰게 되었습니다.^^   위 문제를 설명해주실 때, 처음에 recur으로 접근하신 후 dp로 바꿔서 설명을 해주셨는데요, 15:45 부분에서 설명해주신 내용 중 return으로 인해 계산이 끝나지 않고 이웃 칸으로 이동해서 계속해서 계산을 이어가도록 하는 부분이 return 0 을 return dp[y][x] 로 바꾸는 부분에 해당하는 것인지 질문드립니다.   또한, 마지막에 답을 출력할 때, print(max(map(max,dp))+1 왜 +1을 해주는지 궁금합니다.   [정답 코드] 오늘도 감사합니다~

코딩 센세 · Answer

질문 감사합니다!   문제를 설명해주실 때, 처음에 recur으로 접근하신 후 dp로 바꿔서 설명을 해주셨는데요, 15:45 부분에서 설명해주신 내용 중 return으로 인해 계산이 끝나지 않고 이웃 칸으로 이동해서 계속해서 계산을 이어가도록 하는 부분이 return 0 을 return dp[y][x] 로 바꾸는 부분에 해당하는 것인지 질문드립니다. 네, 맞습니다! 진행하는 공간까지의 모든 경우의 수를 확인해서 최적의 값을 DP에 저장하고, 그 DP 값을 바탕으로 그 다음 값을 계산함으로써 현재까지 최적의 경우의 수 를 바탕으로 계산을 이어갈 수 있습니다 ㅎㅎ 또한, 마지막에 답을 출력할 때, print(max(map(max,dp))+1 왜 +1을 해주는지 궁금합니다. 제가 만든 계산식은 몇 번을 이동했는가 를 계산하고 있는데, 문제에서는 몇 칸 을 이동했는지를 묻고 있기 때문에 +1이 됩니다! ( 시작점을 포함해야해서 그렇습니다 🙂 )

인프런 AI 인턴 · Answer

안녕하세요, 인프런 AI 인턴입니다. 질문하신 내용에 대해 답변 드리겠습니다. 첫 번째 질문에 대한 답변입니다. return 0 을 return dp[y][x] 로 바꾸는 이유는 이미 계산된 dp의 값을 재사용하기 위함입니다. 이는 동적 계획법(Dynamic Programming)의 기본 개념 중 하나인 메모이제이션(memoization)을 활용한 것으로, 한 번 계산된 결과를 저장해두었다가 같은 계산을 반복하지 않도록 하여 프로그램의 효율성을 높이는 방법입니다. 두 번째 질문에 대한 답변입니다. print(max(map(max, dp)) + 1 에서 +1 을 해주는 것은, dp 테이블이 0부터 채워지기 시작하여 실제 최댓값을 구할 때는 +1을 해줘야 정확한 결과를 얻을 수 있기 때문입니다. 쉽게 말해, 문제의 조건이나 구현 방식에 따라 배열의 인덱스는 0부터 시작하지만, 실제 문제에서 요구하는 계산 결과는 1부터 카운트될 수 있으므로 구한 결과에 +1을 해주어야 최종 해답이 됩니다. 정답 코드가 포함된 이미지가 검은색으로 보이는데, 해당 이미지에 오류가 있을 수 있으므로 실제 정답 코드를 확인하시려면 강의 제공자 또는 인프런 고객 지원을 통해 접촉하시는 것을 권장합니다. 추가적인 질문이나 궁금한 점이 있으시다면 언제든지 문의하시기 바랍니다. 오늘도 즐거운 학습 시간 되세요~