DP에서 경우의 수 구할 때 dp[4] += dp[2] 가 되는 원리가 이해가 잘안가요.

Question

1, 2, 3으로 만들 수 있는 경우의 수를 구하는 문제 부분에서 dp[j] += dp[i - j]가 되는 원리가 이해가 안가서 질문드립니다.   1로 만들수 있는 경우의 수를 모두 구하고, 2로 만들수 있는 경우의 수를 만들 때 dp[4]를 만든다면 dp[4] - 기존에 1로 만들 수 있는 경우의 수 (1+1+1+1)에 dp[2]를 더해서 경우의 수를 계산 한다고 설명해주셨는데요.   dp[4]는 (1+1+1+1, 2+1+1, 2+2)는 3가지 경우의 수가 들어가야 하잖아요. 여기서 왜 1로 만든 경우의 수가 (1+1+1+1) 1이 저장된 dp[4]에 (0+2, 1+1)의 경우의 수 2가 저장된 dp[2]를 왜 더하는 걸까요? (2+1+1, 2+2)와 (0+2, 1+1)이 무슨 연관이 있어서 더 해주는지 추가적인 설명부탁드려도 될까요?

큰돌 · Answer

안녕하세요 하얀종이님 ㅎㅎ.   먼저 dp라는 것은 점화식을 잘 이해하는 것 + 이미 계산된 값을 이용하는 것이 핵심입니다.   여기서 dp라는 배열의 의미는 idx에 해당하는 경우의 수의 갯수를 의미합니다.   1. 점화식의 이해 점화식: dp[x] = dp[x-1] + dp[x-2] + dp[x-3] 이 점화식은 다음을 의미합니다. 숫자 x를 만드는 마지막 수가 1일 경우: 이전 숫자인 x-1까지 이미 만들어져 있어야 하므로 dp[x-1] 만큼의 경우의 수를 더함. 숫자 x를 만드는 마지막 수가 2일 경우: 이전 숫자인 x-2까지 이미 만들어져 있어야 하므로 dp[x-2] 만큼의 경우의 수를 더함. 숫자 x를 만드는 마지막 수가 3일 경우: 이전 숫자인 x-3까지 이미 만들어져 있어야 하므로 dp[x-3] 만큼의 경우의 수를 더함. dp[j] += dp[i-j]의 의미 dp[4] 를 계산한다고 가정해볼까요? dp[4]에 저장되는 모든 경우의 수 마지막에 1을 추가해서 4를 만드는 경우: dp[3] 의 모든 경우의 수를 더하겠죠? 마지막에 2를 추가해서 4를 만드는 경우: dp[2] 의 모든 경우의 수를 더하겠죠? 마지막에 3을 추가해서 4를 만드는 경우: dp[1] 의 모든 경우의 수를 더하겠죠? 이를 식으로 풀면, 다음과 같습니다. dp[4] = dp[3] + dp[2] + dp[1] 2. 이미 계산된 값을 활용 왜 dp[4] += dp[2]를 더할까요? dp[4] 에서 마지막 수가 2라고 가정하면, 나머지 4 - 2 = 2를 만드는 경우의 수는 이미 dp[2] 에 계산되어 있습니다. 즉, dp[2]에 저장된 경우의 수는 4에서 2를 마지막으로 추가했을 때 나머지 2를 만드는 모든 가능한 조합 을 포함합니다. 예를 들어 dp[2] = 2라면 이는 2를 다음과 같이 만들 수 있음을 나타내겠죠? 1+1 2 이제 dp[2]에 각각 +2를 추가하면: 1+1+2 2+2 이 두 가지 경우의 수가 dp[4]에 추가되게 됩니다.   또 질문 있으시면 언제든지 질문 부탁드립니다. 좋은 수강평과 별점 5점은 제게 큰 힘이 됩니다. :) 감사합니다. 강사 큰돌 올림.

인프런 AI 인턴 · Answer

안녕하세요, 인프런 AI 인턴입니다. 하얀종이개발자님. 동적 프로그래밍(DP)을 사용하여 특정 숫자를 만드는 방법에 대한 문제를 이해하기 위해서는 DP 배열의 각 요소가 무엇을 의미하는지를 명확히 하는 것이 중요합니다. 이 문제에서 dp[i] 는 숫자 i 를 만드는 경우의 수를 나타냅니다. 먼저, 각 숫자를 몇 개의 1, 2, 3을 조합하여 만들 수 있는지 고려해야 합니다. 예를 들어, 숫자 4로 만들어지는 모든 경우의 수는 숫자 4에서 가능성을 계산할 수 있습니다: &lsquo;1&rsquo;을 마지막으로 두고 숫자 4를 만드는 경우: 이 경우 추가적인 한 &lsquo;1&rsquo;을 사용해 &lsquo;3&rsquo;을 만들 수 있는 방법의 수가 필요합니다. 즉 dp[3] . &lsquo;2&rsquo;를 마지막으로 두고 숫자 4를 만드는 경우: 이 경우 추가적인 &lsquo;2&rsquo;를 사용해 &lsquo;2&rsquo;를 만들 수 있는 방법의 수가 필요합니다. 즉 dp[2] . &lsquo;3&rsquo;을 마지막으로 두고 숫자 4를 만드는 경우: 이 경우 추가적인 &lsquo;3&rsquo;을 사용해 &lsquo;1&rsquo;을 만들 수 있는 방법의 수가 필요합니다. 즉 dp[1] . dp[4] = dp[3] + dp[2] + dp[1] 이라는 점에서 각 경우의 수를 더하는 것이 이해될 것입니다. 따라서 dp[j] += dp[i - j] 는 숫자 j 를 j - x 라는 조합을 더해가는 논리적 방법을 도입하여 가능한 모든 경우를 쌓아가는 것을 의미합니다. 아래 관련 질문들을 통해 더 깊이 있는 이해를 도모할 수 있습니다: 코딩 문제에서 dp 배열 이해하기 다이나믹 프로그래밍 기초 저는 질문자님의 이해를 돕고자 지식공유자님의 기존 답변을 참고하여 유사한 답변 링크를 추천해드리고 있습니다. 현재 베타 기능으로 답변이 만족스럽지 않을 수 있는 점 양해 부탁드립니다. 🙏 추가적으로 궁금한 점이 있으시면, 이어서 질문해 주세요. 곧 지식공유자께서 답변해 주실 것입니다.