인프런 커뮤니티 질문&답변

안녕하세요 ㅎㅎ

사용한 동전의 구성이 같은데, 순서만 다른 것은 같은 경우이다.

>> 이거는 1 2 1이나 1 1 2가 같은 의미라는 의미입니다.

즉, 순서를 신경쓰지 않는 부분입니다. 만약 순서가 상관있다면 순열에 관한 코드가 들어가야 합니다.

어떻게 순서가 같은지 체크가 되는건지 이해가 되지 않아서요.

>> 음.. dp 가 쌓이는 로직을 다시 볼게요.

1인 동전

dp[1] = 1

dp[2] = 1

dp[3] = 1

dp[4] = 1

여기서.

2인 동전 추가가 되었을 때

dp[2] = 2가 됩니다.

1 * 2와 2하나 두개의 경우의 수가 되는 것이죠.

자 순서가 상관있을 법한.

dp[3]을 볼게요.

dp[3] = 1에서

dp[3] = 1 + dp[1]이 되어

dp[3] = 2가 됩니다.

이 의미는

dp[3]을 1로만 채우는 경우의 수 + dp[1]에서 2를 쓰는 경우의 수가 됩니다.

즉,

1 1 1 과 (1 2 또는 2 1) 이 되게 됩니다.

이 의미 자체가 순서와 상관없이 동전을 채우는 코드라고 보시면 됩니다.

        for(int j = temp; j <= k; j ++){  
            dp[j] += dp[j - temp]; 
        }

또 질문 있으시면 언제든지 질문 부탁드립니다.

좋은 수강평과 별점 5점은 제게 큰 힘이 됩니다. :)

감사합니다.

강사 큰돌 올림.