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

www.acmicpc.net/problem/18427

18427번: 함께 블록 쌓기

---

 

풀이)

dp문제중 배낭문제이다.

dp[i][j]=k(i명의 학생들이 j높이 만큼 쌓을 수 있는 경우의수 k)를 만족하는 dp배열 dp[51][51]을 설정해준다.

이떄, 모든 dp[i][0] (1<=i<=N) 은 경우의수가 1가지가 된다.(모든 사람들이 쌓지 않는경우이므로)

 

i명의 학생이 j만큼의 높이를 만들 수 있는 경우의수는 다음과 같다.

 1)i번째 학생이 k번째의 블록을 놓는 경우

   dp[i][j]+=dp[i-1][j-v[i][k]]

   이경우는 k번째 블록을 놔서 j가 되어야 하므로, i-1명이 j-v[i][k]만큼을 쌓은 경우의수와 똑같다고 할 수 있다.

   조심해야 할것은  j-v[i][k]이 0보다 크거나 같아야 한다.

 2)i번째 학생이 블록을 놓지않는 경우

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

   이 경우는 i번째 학생이 0을 놓는것과 같으므로 i-1명이 j만큼 쌓은 경우의 수와 같다

 

이 두가지 경우를 모두 고려하여 문제를 풀어준뒤, dp[N][H]를 출력하면 답이 된다.

 

시간복잡도)

O(N*M*H), 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명이 k를 만들수 있는 경우의수 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;
}