인프런 커뮤니티 질문&답변
작성한 질문수
DP에서 경우의 수 구할 때 dp[4] += dp[2] 가 되는 원리가 이해가 잘안가요.
해결된 질문
작성
·
145
·
수정됨
1
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)이 무슨 연관이 있어서 더 해주는지 추가적인 설명부탁드려도 될까요?
답변 2
1
안녕하세요 하얀종이님 ㅎㅎ.
먼저 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점은 제게 큰 힘이 됩니다. :)
감사합니다.
강사 큰돌 올림.
0
안녕하세요, 인프런 AI 인턴입니다. 하얀종이개발자님.
동적 프로그래밍(DP)을 사용하여 특정 숫자를 만드는 방법에 대한 문제를 이해하기 위해서는 DP 배열의 각 요소가 무엇을 의미하는지를 명확히 하는 것이 중요합니다. 이 문제에서 dp[i]는 숫자 i를 만드는 경우의 수를 나타냅니다.
먼저, 각 숫자를 몇 개의 1, 2, 3을 조합하여 만들 수 있는지 고려해야 합니다. 예를 들어, 숫자 4로 만들어지는 모든 경우의 수는 숫자 4에서 가능성을 계산할 수 있습니다:
‘1’을 마지막으로 두고 숫자 4를 만드는 경우:
- 이 경우 추가적인 한 ‘1’을 사용해 ‘3’을 만들 수 있는 방법의 수가 필요합니다. 즉
dp[3].
- 이 경우 추가적인 한 ‘1’을 사용해 ‘3’을 만들 수 있는 방법의 수가 필요합니다. 즉
‘2’를 마지막으로 두고 숫자 4를 만드는 경우:
- 이 경우 추가적인 ‘2’를 사용해 ‘2’를 만들 수 있는 방법의 수가 필요합니다. 즉
dp[2].
- 이 경우 추가적인 ‘2’를 사용해 ‘2’를 만들 수 있는 방법의 수가 필요합니다. 즉
‘3’을 마지막으로 두고 숫자 4를 만드는 경우:
- 이 경우 추가적인 ‘3’을 사용해 ‘1’을 만들 수 있는 방법의 수가 필요합니다. 즉
dp[1].
- 이 경우 추가적인 ‘3’을 사용해 ‘1’을 만들 수 있는 방법의 수가 필요합니다. 즉
dp[4] = dp[3] + dp[2] + dp[1]이라는 점에서 각 경우의 수를 더하는 것이 이해될 것입니다.
따라서 dp[j] += dp[i - j]는 숫자 j를 j - x라는 조합을 더해가는 논리적 방법을 도입하여 가능한 모든 경우를 쌓아가는 것을 의미합니다.
아래 관련 질문들을 통해 더 깊이 있는 이해를 도모할 수 있습니다:
저는 질문자님의 이해를 돕고자 지식공유자님의 기존 답변을 참고하여 유사한 답변 링크를 추천해드리고 있습니다.
현재 베타 기능으로 답변이 만족스럽지 않을 수 있는 점 양해 부탁드립니다. 🙏
추가적으로 궁금한 점이 있으시면, 이어서 질문해 주세요. 곧 지식공유자께서 답변해 주실 것입니다.
감사합니다. 큰돌님 이해가 너무 잘되게 설명해주셨어요.!!
도움이 많이 됩니다. 꼭 완강하고 수강평 + 별점 5점까지 작성하겠습니다.!!