[C++] 2293 동전1 | DP(Dynamic Programming)

비슷한 문제를 몇번 풀어본 것 같은데, 감이 잘 안 잡혔고

풀이를 읽어봐도 잘 이해가 안 됐었기 때문에

논리를 한번 정리해보려한다.

 

1. 풀이

우선 dp로 저장할 배열의 크기는 n * k + 1이다.

dp[i][j]에 j원을 만드는 데 i번째 동전까지 고려하여 경우의 수를 저장한다. (i = 0, 1, ...)

k가 아닌 k + 1인 이유는 0원을 만드는 경우를 1로 저장하여 뒷쪽 요소에서 활용하기 위함이다.

문제에 주어진 예시를 이용해 자세히 설명해보자.

3 10
1
2
5

dp[1][5]에 5원을 만드는데 1번째 동전까지 고려하여 경우의 수를 저장할 것이다.

즉, 1원과 2원으로 5원을 만드는 경우의 수가 저장된다.

 

이때 1번째 동전인 2원을 기준으로 하여

안 쓰는 경우와 쓰는 경우로 나누어 생각한다.

 

2원을 안 쓰는 경우 - 1원으로만 5원을 만드는 경우의 수인 dp[0][5]를 가져온다.

2원을 쓰는 경우 - 몇개를 쓰는 지에 따라 나누어 생각한다.

1개를 쓴다면, (5원 - 2원 * 1개 = )3원을 1원으로만 만드는 경우의 수인 dp[0][3]을 가져온다.

2개를 쓴다면, (5원 - 2원 * 2개 = )1원을 1원으로만 만드는 경우의 수인 dp[0][1]을 가져온다.

 

5원까지 고려해도 이 논리가 통하는가 의문이 들 수 있으니 dp[2][10]을 설명해보자.

2번째 동전인 5원을 기준으로 하여

5원을 안쓰는 경우 - 1, 2원으로 10원을 만드는 경우의 수이므로 dp[1][10]이다.

5원을 쓰는 경우 -

5원을 1개 쓴다면, (10원 - 5원 * 1개 = )5원을 1, 2원으로만 만드는 경우의 수인 dp[1][5]을 가져온다.

2개를 쓴다면, (10원 - 5원 * 2개 = )0원을 1, 2원으로만 만드는 경우의 수인 dp[1][0]을 가져온다.

 

이때 0원을 만드는 경우의 수는 상식적으로 0이지만, 아까 위에서 1을 저장하겠다고 한 이유를 알 수 있다.

5원을 2개 쓰는 경우 5 5로 10원을 만드는 경우의 수 1을 얻을 수 있는데, dp[1][0]의 값을 가져오기 때문에, 

이곳에 1이 저장되어 있어야한다.

즉, 0원을 만드는 경우의 수는 0이 맞지만 5 5와 같이 뒷쪽 동전만을 활용하여 최종 금액을 만드는 경우 1을 저장한 셈이 된다.

 

 

2. 메모리 초과

위와 같은 논리로 잘 푼 것 같은데

메모리 초과가 났다.

문제를 살펴보니 메모리 제한이 4MB였다.

4 MB = 4 * 10^6 B인데,

int는 4B, n <= 100, k <= 10,000 이므로

dp 배열의 최대 크기만 검색해봐도 초과한다.

4 * 100 * 10,000 = 4,000,000에서 k가 아닌 k + 1로 해야하는 점,

이외에도 다른 자잘한 변수들... 때문이다.

 

그래서 배열의 행을 n개가 아닌 2개로 두기로 했다.

어차피 바로 이전 행만 확인하기 때문에, 모든 행이 다 남아있을 필요가 없다.

% 연산자를 활용하여 위아래로 왔다 갔다 하며 저장했다.

 

자세한 구현 내용은 아래 코드 참고!!

 

 

3. 코드