inflearn logo
강의

강의

N
챌린지

챌린지

멘토링

멘토링

N
클립

클립

로드맵

로드맵

지식공유

10주완성 C++ 코딩테스트 | 알고리즘 코딩테스트

7주차 개념 DP(Dynamic Programming)

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

해결된 질문

241

하얀종이개발자

작성한 질문수 7

1

image.png

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)이 무슨 연관이 있어서 더 해주는지 추가적인 설명부탁드려도 될까요?

c++ 코딩-테스트

답변 2

1

큰돌

안녕하세요 하얀종이님 ㅎㅎ.

 

먼저 dp라는 것은 점화식을 잘 이해하는 것 + 이미 계산된 값을 이용하는 것이 핵심입니다.

 

여기서 dp라는 배열의 의미는 idx에 해당하는 경우의 수의 갯수를 의미합니다.

 

1. 점화식의 이해

점화식:
dp[x] = dp[x-1] + dp[x-2] + dp[x-3]

이 점화식은 다음을 의미합니다.

  1. 숫자 x를 만드는 마지막 수가 1일 경우:

    • 이전 숫자인 x-1까지 이미 만들어져 있어야 하므로 dp[x-1]만큼의 경우의 수를 더함.

  2. 숫자 x를 만드는 마지막 수가 2일 경우:

    • 이전 숫자인 x-2까지 이미 만들어져 있어야 하므로 dp[x-2]만큼의 경우의 수를 더함.

  3. 숫자 x를 만드는 마지막 수가 3일 경우:

    • 이전 숫자인 x-3까지 이미 만들어져 있어야 하므로 dp[x-3]만큼의 경우의 수를 더함.


dp[j] += dp[i-j]의 의미

dp[4]를 계산한다고 가정해볼까요?

  1. 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점은 제게 큰 힘이 됩니다. :)

감사합니다.

강사 큰돌 올림.

1

하얀종이개발자

감사합니다. 큰돌님 이해가 너무 잘되게 설명해주셨어요.!!
도움이 많이 됩니다. 꼭 완강하고 수강평 + 별점 5점까지 작성하겠습니다.!!

0

인프런 AI 인턴

안녕하세요, 인프런 AI 인턴입니다. 하얀종이개발자님.

동적 프로그래밍(DP)을 사용하여 특정 숫자를 만드는 방법에 대한 문제를 이해하기 위해서는 DP 배열의 각 요소가 무엇을 의미하는지를 명확히 하는 것이 중요합니다. 이 문제에서 dp[i]는 숫자 i를 만드는 경우의 수를 나타냅니다.

먼저, 각 숫자를 몇 개의 1, 2, 3을 조합하여 만들 수 있는지 고려해야 합니다. 예를 들어, 숫자 4로 만들어지는 모든 경우의 수는 숫자 4에서 가능성을 계산할 수 있습니다:

  1. ‘1’을 마지막으로 두고 숫자 4를 만드는 경우:

    • 이 경우 추가적인 한 ‘1’을 사용해 ‘3’을 만들 수 있는 방법의 수가 필요합니다. 즉 dp[3].
  2. ‘2’를 마지막으로 두고 숫자 4를 만드는 경우:

    • 이 경우 추가적인 ‘2’를 사용해 ‘2’를 만들 수 있는 방법의 수가 필요합니다. 즉 dp[2].
  3. ‘3’을 마지막으로 두고 숫자 4를 만드는 경우:

    • 이 경우 추가적인 ‘3’을 사용해 ‘1’을 만들 수 있는 방법의 수가 필요합니다. 즉 dp[1].

dp[4] = dp[3] + dp[2] + dp[1]이라는 점에서 각 경우의 수를 더하는 것이 이해될 것입니다.

따라서 dp[j] += dp[i - j]는 숫자 j를 j - x라는 조합을 더해가는 논리적 방법을 도입하여 가능한 모든 경우를 쌓아가는 것을 의미합니다.

아래 관련 질문들을 통해 더 깊이 있는 이해를 도모할 수 있습니다:

저는 질문자님의 이해를 돕고자 지식공유자님의 기존 답변을 참고하여 유사한 답변 링크를 추천해드리고 있습니다.
현재 베타 기능으로 답변이 만족스럽지 않을 수 있는 점 양해 부탁드립니다. 🙏
추가적으로 궁금한 점이 있으시면, 이어서 질문해 주세요. 곧 지식공유자께서 답변해 주실 것입니다.

코딩테스트 참고문헌 질문

0

38

2

4-P 질문 있습니다.

0

40

3

4-N 문제 수정 요청

0

32

1

2-T 질문

0

39

1

코딩 살구클럽 가입 문의

0

74

2

코딩살구클럽 가입문의

0

80

2

3-K private case 질문

0

76

2

안녕하세요. 코딩살구클럽 문의드립니다!

0

88

2

7:41 듣다가 질문합니다

0

93

2

코드 리뷰 요청드립니다!

0

89

2

코딩살구클럽 계정 문의

0

84

2

SK하이닉스 대비 강의수강

0

226

3

코딩살구클럽 등록부탁드립니다.

0

82

2

7-F 재귀로 풀시 런타임애러

0

82

1

1-N 문제 질문입니다. (+ 채점오류)

0

86

2

코딩살구클럽 가입 확인 부탁드립니다.

0

88

2

직장인 코테 합격 공부방법 문의

0

136

2

코딩살구클럽 가입 방법

0

104

2

6-H 체점 관련 질문

0

83

1

채점서버 연결 관련 질문입니다

0

111

2

삼성 s직군

0

95

1

삼성 코테 없어짐

0

241

1

코딩살구클럽 가입부탁드립니다

0

93

2

코딩살구클럽 가입 요청 확인부탁드립니다

0

77

2