11726 런타임 질문

Question

안녕하세요 강사님,   백준 11726번 관련 질문 드립니다.   노션에 나온 정답지는 # input N = int(input()) # solve dp = [0] * (N + 2) dp[1] = 1 dp[2] = 2 for n in range(3, N + 1): dp[n] = (dp[n-1] + dp[n-2]) % 10007 print(dp[N]) 으로 되어있습니다. 그런데 강의에서는 dp = [0] * (N + 2) 부분이 dp = [0] * (N + 1) 로 되어있습니다.   백준에 dp = [0] * (N + 1) 로 제출하면 런타임 에러가 발생하는데, 그 이유를 알 수 있을까요? dp[N]까지 접근하는건데, 0번째 인덱스를 고려한 N+1이아닌, N+2는 왜 필요한지 모르겠습니다. (강의나 노션에 추가 설명이 보이지 않아서 여쭤봅니다)   감사합니다.

알리 Ally · Answer

안녕하세요. 타이거님!   N에 상관없이 기본적으로 dp[0]과 dp[1]을 초기값 처리할 때 접근하기 때문입니다. dp 배열의 크기를 N + 1로 한다면 N = 0일 때, dp[1]에 접근하지 못하기 때문에 런타임 에러가 나게 됩니다. 즉, N = 0일 때도 dp[1]까지 접근할 수 있게 하기 위해서 dp 배열의 크기를 N + 2로 했다고 생각하시면 됩니다.   비슷한 상황에 대한 설명이 섹션2의 '재귀함수 이해하기 [문제풀이] : BOJ 10870' 강의의 4:34 - 5:02 부분 에 설명이 나와 있으니 참고하면 될 것 같습니다. 추가로 해당 부분에 대한 설명을 강의 자료에 추가해 놓겠습니다.   또 궁금하신 점 있으시면 언제든 질문 부탁드립니다. 감사합니다. :)

인프런 AI 인턴 · Answer

안녕하세요, 인프런 AI 인턴입니다. 타이거님께서 질문하신 백준 11726번 문제의 런타임 에러에 대한 원인은 DP 배열의 길이가 문제의 요구사항을 충족하지 못하기 때문이라고 예상됩니다. 백준 문제에서는 피보나치 수열과 유사한 DP 문제의 특성상, N이 1 또는 2일 경우에도 문제 없도록 미리 초기화 가 필요합니다. 기본적으로 dp = [0] * (N + 2) 는 인덱스 에러를 방지하기 위한 안전 조치로, N이 작을 때도 배열 인덱스 접근 시 문제가 없도록 설계된 것입니다. dp = [0] * (N + 1) 로 설정하면, 예를 들어 N이 2일 때 dp[2] 까지는 맞지만, 만약 루프에서 dp[n-1] 과 dp[n-2] 까지의 접근이 필요한 경우, 인덱스를 초과하게 되는 경우가 발생할 수 있습니다. 따라서 dp = [0] * (N + 2) 로 배열을 선언하여 dp[n-2] 까지의 계산에 대비하는 편이 안전한 방법입니다. 추가적으로 이러한 문제들은 각 언어의 인덱싱 특성과 문제에서 요구하는 초기값 설정의 이해가 필요합니다. 백준 문제에서는 다양한 언어로 실험하며 초기 설정을 기반으로 런타임 에러를 해결하는 것이 중요합니다. 질문자님의 이해를 돕고자 관련 내용을 참고할 수 있는 기존 답변 링크를 추천드립니다: - 백준 DP 문제와 인덱스 에러 해결 게시글을 참조하여 배열 초기화에 대한 다양한 방법과 각 경우의 수에 대한 상세 설명을 확인해 보세요. 저는 질문자님의 이해를 돕고자 지식공유자님의 기존 답변을 참고하여 유사한 답변 링크를 추천해드리고 있습니다. 현재 베타 기능으로 답변이 만족스럽지 않을 수 있는 점 양해 부탁드립니다. 🙏 추가적으로 궁금한 점이 있으시면, 이어서 질문해 주세요. 곧 지식공유자께서 답변해 주실 것입니다.