배수 공사

//15817 - 배수공사
 
#include <iostream>
using namespace std;
 
int N, K;
int arr[100];
int arr2[100];
int cache[100][10001];
 
void init()
{
    cin >> N >> K;
    for(int i = 0; i<N; ++i)
        cin >> arr[i] >> arr2[i];
    for(int i = 0; i<N; ++i)
        for(int j = 0; j<=K; ++j)
            cache[i][j] = -1;
}
 
int dp(int idx, int length)
{
    if(length == K)
        return 1;
    if(length > K) return 0;
    if(idx == N) return 0;
    int& ret = cache[idx][length];
    if(ret != -1)
        return ret;
    ret = 0;
    for(int num = 0; num <= arr2[idx]; ++num)
        ret += dp(idx+1, length + arr[idx]*num);
    return ret;    
}
 
int main()
{
    init();
    cout << dp(0, 0);
}

 

 

 

 

 

 

acmicpc.net/problem/15817

15817번: 배수 공사

 

 

 

 

 

 

배수 공사

재귀함수에 메모이제이션을 사용했습니다.

dp(idx, length) : length길이까지 파이프를 만들었고, 현재 idx번째 파이프를 사용할 차례