[백준] 18427-함께 블록 쌓기(C++), 배낭알고리즘

문제링크:www.acmicpc.net/problem/18427

18427번: 함께 블록 쌓기

 

무난한 난이도의 dp 문제였습니다.

 

한 학생당 최대 1개의 블록라는 조건을 통해서 배낭문제 알고리즘으로 해결할 수 있습니다.

 

dp[i][j] 는 i번째까지 학생에게 j높이에서의 최대 경우의수라고 할때, 아래와 같이 됩니다. (초기화 작업으로 0일때는 1로 지정)

 

0	1	2	3	4	5
1	0	1	1	0	1
1	0	1	2	0	3
1	1	2	4	3	6

첫번째 학생이 2,3,5니까, dp[1]은 101101이 되고 두번째 학생을 포함하면 101203이되고... 

그러면 학생이 가진 블록뺀 dp[i-1][j-vec[i][k]] 만큼씩 더해주고 그 이후에 dp[i-1][j] 을 더해주면 해결됩니다.

 

 

조심할 점은  if (j >= vec[i][k]) 일때 dp[i - 1][j - vec[i][k]]을 수행하여야 한다는 점이다. 

아래는 정답코드입니다.

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

int n, m, h;
vector <int> vec[51];
int dp[51][1001] = { 0, };

int main() {
	ios_base::sync_with_stdio(0);
	cin.tie(0), cout.tie(0);

	cin >> n >> m >> h;
	cin.ignore(1);

	for (int i = 1; i <= n; i++) {
		string temp;
		getline(cin, temp, '\n');
		
		for(int j=0;j<temp.size();j++)
			if(temp[j]==' '||j==0)
				vec[i].push_back(stoi(&temp[j]));

			
	}
	

	
	//solve

	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 < vec[i].size(); k++) {
				
				if (j >= vec[i][k]) {
					dp[i][j] += dp[i - 1][j - vec[i][k]];
					dp[i][j] %= 10007;
				}
			}		
			dp[i][j] += dp[i - 1][j];
			dp[i][j] %= 10007;
		}
	}


	cout << dp[n][h] << endl;


	return 0;
}