[백준] 2293번: 동전 1 풀이 및 해설(C++)

https://www.acmicpc.net/problem/2293

2293번: 동전 1

 

풀이

 

2차원 배열을 사용하는 dp로 접근했다.

가능한 돈의 경우의 수를 동전별로 따로 접근한다. 행에는 동전, 열에는 목표하는 원을 만들고, 그에 따라 가능한 경우의 수를 할당하였다.

배열의 열을 i라고 하고, 현재 사용하는 동전 행을 j라고 하자. 그리고 현재 n원 짜리 동전으로 계산하고 있다면 다음과 같은 점화식이 나온다.

dp [i][j]=dp [i-1][j]+dp [i][j-n]

현재 dp에 할당되는 값은 {이전까지 다른 동전을 사용해 나왔던 경우의 수 arr [i-1][j]}+{n원짜리 동전을 이전보다 1개 덜 사용했을 때의 경우의 수 arr [i][j-n]} 이기 때문이다.  

 

점화식이 성립되지 않는 초기항 부분들, 처음 동전을 처리하는 첫 열과 각 n원짜리 행에서 n원 이전의 값들만 따로 처리해 준다.

각행에서 인덱스 n으로, n원으로 시작되는 부분들만 1을 추가해 준다. 이제 이 동전을 사용한다고 정했기 때문이다.

 

그러면 다음과 같은 2차원 배열이 나오고 제일 마지막에 나온 10을 출력하면 된다.

	0	1	2	3	4	5	6	7	8	9	10
5원	0	0	0	0	0	1	0	0	0	0	1
2원	0	0	1	0	1	1	1	1	1	1	2
1원	0	1	2	2	3	4	5	6	7	8	10

 

그런데 이렇게 2차원 배열로 짰더니 메모리 초과가 나버렸다.

 

메모리 초과라니...

 

 

문제에서 제한하는 메모리의 양은 4MB, 여기서 사용하는 2차원 배열은 101(n)*10001(k)*4byte(int)로 4메가바이트를 살짝 넘어간다.

4MB

 

메모리초과를 막기 위해서는 2차원 배열이 아닌 1차원 배열을 써야 한다.

 

점화식을 다시 한번 생각해 보자.

dp [i][j]=dp [i-1][j]+dp [i][j-n]

 

dp [i-1][j]는 결국 같은 위치에 있던 동일한 값을 가져오는 것이다.

그렇다면 점화식을 다음과 같이 바꾸어도 상관이 없다!

dp [i][j]+=dp [i][j-n]

2차원 배열을 쓰는 이유가 단순히 아직 수정되지 않은 이전값을 가져오는 것이라면 1차원 배열로 얼마든지 바꿀 수 있다.

다시 말해 2차원 배열에서 LCS 문제처럼 좌대각 위의 값을 가져오는 것이 아니라 그냥 바로 위의 값이면 값을 처리할 때 아직 변동되지 않은 값이기 때문에 1차원 배열로도 구현할 수 있는 것이다!

 

idx	0	1	2	3	4	5	6	7	8	9	10
결과	0	1	2	2	3	4	5	6	7	8	10

 

 

해답 코드는 아래와 같다.

 

해답 코드

#include <iostream>
using namespace std;

int main()
{
    int coins,goal;
    int coin[101];
    int dp[10001]={0};
    cin>>coins>>goal;
    for(int i=0; i<coins; i++){
        cin>>coin[i];
    }
    int k=coin[0];        
    while(k<goal+1){
        dp[k]++;
        k+=coin[0];
    }
    for(int i=1; i<coins; i++){
        int n=coin[i];
        if(n<=goal){
        dp[n]++;
        }
        for(int j=n+1;j<goal+1; j++){
            dp[j]+=dp[j-n];
        }
    }
    cout<<dp[goal];
    return 0;
}

 

헤맸던 부분

목표액보다 더 큰 단위의 동전이 들어올 때 outofbounds error가 났다.

그래서 dp [n]++ 이전에 n <=goal이라는 조건문을 넣어주었다.