DP 알고리즘 (1)

알고리즘 공부를 하면서, 언젠가는 이해를 하고 구현을 해봐야지 했던 것이 다이나믹 프로그래밍 DP였다.

큰 문제를 작은 문제의 결과값을 이용해서 계속 풀어나가는 알고리즘인데, 대표적인 문제로는 피보나치수열을 DP배열에 저장하면서 푸는 방법이 있다.

가장 중요한 것이, 점화식을 빨리 찾아내는 것이라고 생각한다.

백준 18427번 문제를 풀어보았다.

이 문제는 몇번째 학생의 높이가 h일때의 경우의수를 계속 더해가면서, 내가 구하고자 하는 n번째 학생 h높이일 때 최종적으로 다 더한 경우의 수를 DP배열에서 반환해주면 된다.

 

이 문제에서는 경우의 수를 더해가는 것이 중요했는데

예제를 기준으로 보면 처음 DP테이블 초기화는 이렇게 했다.

dp[i][0] ~ dp[i][h] 까지 채우면서, i가 N까지 반복을 한다

n \ h	0	1	2	3	4	5
0	1	0	0	0	0	0
1	1	0	0	0	0	0
2	1	0	0	0	0	0
3	1	0	0	0	0	0

 

높이가 0 일때 1, 2, 3번 학생 모두 높이가 0인 탑을 쌓는 경우는, 고르지 않는 경우가 있기 때문에, 1로 설정한다.

n \ h	0	1	2	3	4	5
0	1	0	0	0	0	0
1	1	0	1	1	0	1
2	1	0	0	0	0	0
3	1	0	0	0	0	0

 

dp[i][j] 칸에서의 경우는 두가지

1. j에 해당하는 블록을 i번째 학생이 갖고 있을 때 고르는 경우

2. 고르지 않는 경우

 

1번에 해당하는 경우는

내부에 for을 하나 추가해서, i번째 학생의 가진 블록을 순회하면서,

if(j >= blocks[i][k]) dp[i][j] = (dp[i][j] + dp[i-1][j-blocks[i][k]]) % 10007;

즉 현재 조사하는 높이 j가 현재 보고있는 학생의 가진 블록보다 크거나 같으면, 계산을 수행하는데,

j-blocks[i][k]번째를 dp에서 찾아서 더해주는 이유는, (H - 현재 블록 높이) 까지의 경우의 수를 더해줘야 하기 때문이다.

이후 i번째 학생이가진 모든 블록에 대해 조사가 끝나면,

dp[i][j] = (dp[i][j] + dp[i-1][j]) % 10007;

 

를 수행해주는데, 이건 아까 말한 2번조건, 고르지 않았을때 dp테이블에서 처리해주는 방식이다.

전체 코드

#include <iostream>
#include <vector>
#include <sstream>

using namespace std;
vector<int> blocks[51];
int dp[51][1001] = {0, };
/*
2 3 5
3 5
1 2 3

dp table(경우의 수)
nh0 1 2 3 4 5
0 1 0 0 0 0 0
1 1 0 1 1 0 1
2 1 0 1 2 0 3
3 1 1 2 4 3 6
*/


int N, M, H;

int main(){
  cin >> N >> M >> H;
  
  cin.ignore();
  for(int i = 1; i <= N; i++){
    string str;
    getline(cin, str);
    stringstream sstr(str);
    int num;
    while(sstr >> num) blocks[i].push_back(num);
  }
  //dp테이블에서 아무것도 선택하지 않았을 경우 즉 높이가 0으로 주어졌을때 선택하지 않으면 되므로 1로 초기화
  for(int i = 0; i <= N; i++) dp[i][0] = 1;
  //dp테이블에서 1번째 학생부터 검사 시작
  for(int i = 1; i <= N; i++){
    //dp테이블에서 i번째 학생의 행을 채우기(주어진 높이에 따라서)
    for(int j = 1; j <= H; j++){
      //학생이 가진 각 블록에 대해 검사
      for(int k = 0; k < blocks[i].size(); k++){
        //j-blocks[i][k]를 하는 이유 -> (H - 현재 블록 층수)까지의 경우의 수를 더해주는 것
        if(j >= blocks[i][k]) dp[i][j] = (dp[i][j] + dp[i-1][j-blocks[i][k]]) % 10007;
      }
      dp[i][j] = (dp[i][j] + dp[i-1][j]) % 10007;
    }
  }
  cout << dp[N][H] % 10007;
}