[백준알고리즘] 2293번: 동전 1 -C

[백준알고리즘] 2293번: 동전 1 -C

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

 

단계별로 풀어보기 마지막 '동적 계획법 1'의 마지막 문제였다. 그래서 기쁜 마음으로 봤는데 생각보다 쉬워서 흡족했다..ㅎㅎ

 

처음에는 일단 가볍게 동전 가치의 내림차순으로 정렬한 후에 재귀를 사용해서 해봤다.

역시나 시간초과가 발생했다.

 

그래서 다음에 사용한건 nsize와 target의 크기를 입력받아 nsize x target행렬을 만든 것이다. 이때부터는 점화식을 사용했기 때문에 내림차순 정렬이 필요없어진다. 사용했던 점화식은 다음과 같다.

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

(i번째 동전없이 j가치를 만들 수 있는 방법의 수) + (i번째 동전을 포함해서 j의 가치를 만들 수 있는 방법의 수)

 

그런데 이렇게만 하더라도 메모리 초과가 발생한다. n의 최대 100 k가 최대 10000 이기 때문에 n x k 정수행렬의 크기만해도 벌써 4MB가 되기 때문이다.

 

그래서 줄일 방법을 생각하다가 점화식이 어차피 i번째 열은 i - 1번째 열까지만 사용하는 것을 알았다. 그래서 이중 배열을 딱 2 x target 크기로 만들어서 사용했다.

 

점화식을 구성하는 것이 쉽기 때문에 바로 코드만 보이겠다.

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

int main(void){
    int nsize = 0, target = 0;
    int *nlist;
    int *dp[2];
    int i = 0, j = 0, base = 0, idx = 0;

    /* input */
    scanf("%d", &nsize);
    scanf("%d", &target);

    /* initialize */
    nlist = (int *)malloc(sizeof(int) * (nsize + 1));
    dp[0] = (int *)malloc(sizeof(int) * (target + 1));
    dp[1] = (int *)malloc(sizeof(int) * (target + 1));
    memset(nlist, 0, sizeof(nlist));
    memset(dp[0], 0, sizeof(dp[0]));
    memset(dp[1], 0, sizeof(dp[1]));
    dp[0][0] = dp[1][0] = 1;

    for(i = 1; i <= nsize; i++){
        scanf("%d", &nlist[i]);
    }
    
    /* dynamic programming */
    for(i = 1; i <= nsize; i++){
        base = nlist[i];
        idx = i % 2;     // dp[0] or dp[1] 
        
        for(j = 1; j <= target; j++){
            if(j < base){
                dp[idx][j] = dp[(idx + 1) % 2][j];
            }
            else{
                dp[idx][j] = dp[idx][j - base] + dp[(idx + 1) % 2][j];
            }
        }
    }

    printf("%d\n", dp[idx][target]);

    free(nlist);
    free(dp[0]);
    free(dp[1]);
    return 0;
}

 

 

 

잘못된 점이나 부족한 점 지적해주시면 감사하겠습니다