문제 이해 단계
https://www.acmicpc.net/problem/18427
N명의 학생이 각각 최대 M개의 블록을 가지고 있다.
학생들이 가지고 있는 블록은 전부 길이가 다르다.
예를 들어 1번 학생이 높이가 2,3,4인 블록을
가지고 있는 것처럼 모두 길이가 다르다.
높이 H가 주어지는데,
N명의 학생이 순서대로 최대 1개를 사용해서 블록을 쌓을 때
정확히 높이 H가 될 수 있는 경우의 수를 구하는 문제
문제 접근 단계
일단 해당 문제의 키워드에 주목했다.
1. 최대 1개까지 쓸 수 있다.(안 써도 된다)
2. 1번 학생 ~N번까지 순차적으로 블록을 쌓는다.
1번 조건에서 해당 문제가 여러 가지 경우의 수로 나뉘는 것을
계산하는 문제라는 것을 알았고,
무엇보다도 2번째 조건에서 순서가 고정되어 있다는 것을 알았다.
순서가 고정되어 있다는 소리는,
전개 방식에 따라 일정한 값
즉, 고정된 값이 나오게 할 수 있다는 소리이다.
그래서 해당 문제가 동적 계획법(DP)으로 푸는 것이
효율적이겠다는 가정을 가지고 시작했다.
DP로 풀기 위해서는 점화식을 세워야 한다.
점화식을 세우기 위해서는 일반화를 해봐야 하니까
여러 가지 경우를 상정하기 위해 한번 시뮬레이션을 돌려보자
1번 학생: 2, 3, 5
2번 학생: 3, 5
3번 학생: 1, 2, 3
이 상태에서 2번 학생의 3cm 블록을 탐색한다고 생각해 보자.
(1번 학생에서의 작업은 끝난 상태)
경우의 수는 2가지가 있을 것이다.
1. 필요한 경우
2. 필요하지 않은 경우
필요한 경우는 높이가 H보다 작을 때 일 것이다.
이 말을 돌려 말하면 3cm를 사용하려면
H-3cm의 공간은 있어야 한다는 소리이다.
필요하지 않은 경우는 간단하다.
이미 높이가 H 초과이거나 할 경우이다.
이럴 경우에는 어차피 이전 경우의 수가 최대 경우의 수가 되기 때문에
이전 값이 현재 값의 최대 경우의 수가 된다.
여기까지 생각하게 되니,
대표적인 알고리즘 하나랑 엇비슷하다는 생각이 들었다.
어떤 물건을 넣기 위해서는 해당 공간이 필요로 하고
그 물건을 쓰지 않을 경우 이전 결과가 현재 결과의 답이 되는 구조
바로 배낭 문제(Knapsack Problem)이다.
이 점을 아니까, 어느 정도 길이 보이기 시작했다.
이 문제는 배낭 문제를 응용해서 풀면 되리라는 생각이 들었다.
배낭문제와 비슷하게 dp 식을 세우면 된다고 생각했다.
해당 문제에서 배낭 알고리즘처럼
현재 조사하고 있는 순서와 높이를 변수로 두어 2차원 배열을 만들겠다.
dp [K][H] :
K번째 학생들을 가지고 높이가 H인 탑을 만들 수 있는 경우의 수
이렇게 정의하고 다양한 경우의 수를 생각해 보겠다.
1번 학생: 2, 3, 5
2번 학생: 3, 5
3번 학생: 1, 2, 3
다시 한번 이 경우의 수에서
2번 학생의 관점에서 생각해 보겠다.
1번 학생을 거쳐 2번 학생을 선택할 때
총 3가지 선택지가 있다.
1. 3cm 블록 선택
2. 5cm 블록 선택
3. 아무 블록도 선택하지 않는다.
하나씩 생각해 보자.
3cm나 5cm 블록을 선택하려면 어떻게 해야 할까?
물론 H가 그만큼 높아야 한다.
그리고 H-3, H-5만큼의 공간이 남아있어야 한다.
그래야만 정확히 높이가 H가 될 수 있기 때문이다.
아무 블록도 선택하지 않는 경우는?
그냥 그대로이다.
이를 일반화해 보자.
dp [K][H]를 구할 때 아무것도 선택하지 않을 경우는
dp [K][H] = dp [K-1][H]
왜냐하면 높이가 변하지 않기 때문에
H는 그대로이고 최대 경우의 수도
이전 경우의 수가 최대일 것이기 때문이다.
그렇다면 선택하는 경우는?
dp [K][H]
=
(dp [K-1][블록의 길이]) + (dp [K-1][블록의 길이]) +...
이렇게 될 것이다.
왜냐하면 선택하는 블록만큼
경우의 수는 많아지기 때문이다.
물론 배열이 0 이하인 경우
즉, 길이가 음수로 가는 경우는 포함되지 않는다.
이 두 가지를 점화식으로 알고리즘으로 만들면 된다.
문제 구현 단계
for(int i = 1; i <= N; i++){
string str;
getline(cin,str);
stringstream sstr(str);
int num;
while(sstr >> num) block[i].push_back(num);
}
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 < block[i].size(); k++){
if(j>=block[i][k]) dp[i][j] = (dp[i][j]+dp[i-1][j-block[i][k]]) % 10007;
}
dp[i][j] = (dp[i][j]+dp[i-1][j])%10007;
}
}
cout << dp[N][H];유심히 봐야 할 코드는 while문 아래부터다.
일단 dp 2차원 배열에서 높이가 0일 때는
다 1로 해줬는데, 이렇게 안 해주면
애초에 dp 연산이 성립이 되지 않기 때문에 임의로 설정해 줬다.
그리고 이중반복문을 사용하여
바깥에 있는 반복문은 학생의 번호를 순서대로
안에 있는 반복문은 높이를 1에서 H까지를 반복한다.
block [i]. size()는 학생이 가지고 있는 블록의 개수만큼 반복하는 것인데,
그 블록의 높이가 현재 블록의 높이인 j보다
같거나 작을 때 위에서 말했던
dp [K][H] = (dp [K-1][블록의 길이]) + (dp [K-1][블록의 길이]) +...
연산을 해준다.
%10007를 해주는 것은
문제 조건해서 해주라고 해서 해주는 것이다.
밑에 있는 dp [i-1][j]는
해당 학생의 블록을 아예 넣지 않았을 때의 경우의 수이다.
최종적으로 얻는 것은
dp [N][H] 즉, N학생까지 조사했을 때 H높이이다.
아래는 최종 코드를 올리겠다.
#include <iostream>
#include <sstream>
#include <vector>
using namespace std;
int dp[51][1001];
vector<int> block[51];
int main(){
cin.tie(0); cout.tie(0); ios::sync_with_stdio(false);
int N,M,H;
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) block[i].push_back(num);
}
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 < block[i].size(); k++){
if(j>=block[i][k]) dp[i][j] = (dp[i][j]+dp[i-1][j-block[i][k]]) % 10007;
}
dp[i][j] = (dp[i][j]+dp[i-1][j])%10007;
}
}
cout << dp[N][H];
}여기서 입력을 받을 때 getline()을 사용했는데,
한 줄을 입력받는 것이다.
string class에 있는 getline을 사용하는 건데
이걸 사용할 때 유의할 점이 있는데
int n;
cin >> n;
getline(cin, str)
이렇게 사용하면 에러가 뜨기 때문에
중간에 cin.ignore()을 섞어줘야 한다.
시행착오
해당 문제를 풀기 전에
배낭 알고리즘에 대한 분석을 하고 발표를 했었다.
덕분에 배낭알고리즘을 깊게 이해했었고
이 문제에 적용 및 응용할 수 있었다.
덕분에 로직을 생각하는 데는 쉬웠다.
하지만 역시 구현이 문제였다.
Dp문제가 한번 로직이 꼬이니까 머리가 정말 아프더라
역시 구현 문제를 좀 많이 풀어봐야겠다.