문제

동전 1

풀이

dp배열은 n개를 만드는데 경우의 수를 값으로 넣습니다. 그래서 n개를 만들때 경우의수 k는 dp[n] = k 로 나타내기로 합니다 다이나믹 프로그래밍의 경우에는 규칙성을 파악해보기로 하는데 예시에서 주어진 1, 2, 5를 가지고 문제를 풀어볼수있는데요

dp[0] = 1; // 1개
dp[1] = 1; // 1 => 1개
dp[2] = 2; // 1,1 / 2 => 2개
dp[3] = 2; // 1,1,1 / 2,1 => 2개
dp[4] = 3; // 1,1,1,1 / 2,1,1 / 2,2 => 3개
dp[5] = 4; // 1,1,1,1,1 / 2,1,1,1 / 2,2,1 / 5 => 4개
...

이렇게 경우의 수를 나열하다 보면 규칙성이 존재함을 알수 있습니다.
바로 dp[n]은 이전의 dp[n]의 값에 영향을 받는 다는 것입니다.

일단 모든 n은 1로만 이루어질 수 있기에 모든 경우에 수(dp[n])에 +1를 기본적으로 해줍니다
또 2를 포함한 경우의 수는 dp[n] n은 2보다 큰 경우의 수 전부에 포함될것입니다. 그렇기 때문에 2이상인 경우 +1를 반복적으로 해주는 작업이 필요합니다.

또 dp[4] 의 경우인 4의 경우에는 2로만 이루어진 경우에 수가 딱하나더 추가가 될것입니다. 이 경우의 수를 나열하면서 규칙을 찾아보면 다음과같습니다.

dp[n] = dp[n] + dp[n - arr[i]];

더해지는 dp[n]은 이전의 dp[n]의 값을 말합니다. 그래서 이전의 값에 해당하는 것을 가져와서 dp[n - arr[i]] 을 더하면 이것이 바로 n이 가지는 값이겠습니다.

이 수식을 가지고 전개합니다. 잘 이해했다면 정말 쉬운문제였겠지만 저는 이부분에 도달하는데도 오래걸렸기 때문에 ㅠㅠ

// 동전 n개를 차례대로 넣습니다.
for (int i = 0; i < n; i++) {
	// 가치 k가될때까지 경우의 수를 계속 더해줍니다.
	for (int j = arr[i] ; j <= k; j++) {
    	dp[j] += dp[j - arr[i]];
    }
}

전체 코드

전체 코드