[백준OJ] 18427번 함께 블록 쌓기

www.acmicpc.net/problem/18427

18427번: 함께 블록 쌓기

---

 

풀이)

dp문제+배낭문제이다. dp[i][j]=k 를 i명이 h높이를 만들 수 있는 경우의 수를 k라고 하자. 

i명의 사람이 j높이 만큼 쌓을 수 있는 경우의 수는, i-1명이  j-(i번째 사람이 들고있는 현재블록의 높이) 만큼 쌓을 수 있는 경우의 수와 동일하다.

예를들어 4번째 사람이 들고있는 블록의 높이가 2,4라고 했을 때, 4명의 사람이 10만큼의 높이를 쌓는 경우의 수는 3명이 8만큼 쌓은 경우의 수+3명이 6만큼 쌓은 경우의 수가 된다.

왜냐하면 3명이 8만큼쌓고 4번째사람이 2를 올렸을때 10이되고, 3명이 6만큼 쌓고 4번째 사람이 4를 올렸을때 10이 되기 때문이다.

따라서 dp[i][j]=dp[i][j]+dp[i-1][j-(i번째 사람이 들고있는 블록의 높이)] 가 된다.

 

 

시간 복잡도)

O(N*M*H)

 

코드)

#include<iostream>
#include<algorithm>
#include<string>
using namespace std;

int n,m,h;
vector<int> v[51];
int dp[51][1001]={0};//dp[i][j]=k, i명이 h를 만들수 있는 경우의수 k


//수행시간 O(n*m*h)
void solve(){
    //0을 만드는 경우는 모두 1개씩
    for(int i=0;i<=n;i++){
        dp[i][0]=1;
    }
    
    for(int i=1;i<=n;i++){
        for(int j=1;j<=h;j++){
            for(int k=0;k<v[i].size();k++){
                //사람이 한명 더 줄은 상태의 j-v[i][k]높이의 경우의수를  모두 더해준다.
                if(j-v[i][k]>=0){
                    dp[i][j]+=dp[i-1][j-v[i][k]];
                    dp[i][j]%=10007;
                }
            }
            //i번째 사람이 안들어갔을때도 완성이 될 수 있으므로 더해준다
            dp[i][j]+=dp[i-1][j];
            dp[i][j]%=10007;
        }
    }
    
}

int main() {
    ios_base :: sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
    cin>>n>>m>>h;
    cin.ignore(1);
    for(int i=1;i<=n;i++){
        string data;
        getline(cin,data);
        int temp=0;
        for(int j=0;j<data.size();j++){
            if(data[j]==' '){
                v[i].push_back(temp);
                temp=0;
            }
            else{
                temp=temp*10+(data[j]-'0');
            }
        }
        if(temp!=0)    v[i].push_back(temp);
    }
    
    solve();
    cout<<dp[n][h]<<"\n";
	return 0;
}