1. Top-Down문제에서 대놓고 그대로 구현하면 값을 구하는데 오래 걸린다고 한다.DP 1번 문제였던 피보나치와 마찬가지로 너무 많은 재귀함수가 호출되기 때문이다.그러면.. 해결방법은 재귀함수 호출을 줄이면 된다. 뭘 이용해서 ? Memorization !
이 문제에선 배열에 저장된 값이 0이 될 수 있기 때문에, 처음에 배열에 모든 값을 -1로 초기화해주자.
왜 ?
예를 들어, w[20][20][20]을 구하기 위해서 w[20][20][19]에 접근했더니 w[20][20][19]에 저장된 값이 0이라고 가정해보자.
재귀함수를 통해 이미 계산된 값이라면 더 돌아볼 것도 없이 0을 리턴해주면 되지만, 초기화된 값이었다면 w[20][20][19] 값을 구하기 위해 또 다른 재귀함수가 실행될 것이다.
자... 이 저장된 0은 재귀함수를 통해 이미 계산된 값인지 프로그램 실행 때 초기화된 값인지.. 어떻게 알 것인가 ? 모른다;; 그렇기 때문에, 아직 계산되지 않은 원소라는 의미에서 배열 안에 모든 원소를 -1로 초기화시켜주자.
이제 재귀함수만 작성하면 끝난다.재귀함수 내에서 w[a][b][c]에 저장된 값이 -1인지 체크해보자. -1이라면 문제에서 준 점화식을 통해 값을 계산하면 될 것이고, -1 아니라면 이미 계산된 값이기 때문에 그 값을 바로 리턴하자.
그럼 끝! 이 아니다. a, b, c 중 하나라도 0보다 작거나 같은 경우와 20보다 큰 경우는 따로 처리해주어야하기 때문에, w[a][b][c]에 먼저 접근하지 말고 a, b, c의 값을 먼저 체크 해주어야 한다.
무슨 소리인지 모르겠다면 코드로 한번 보자.
#include <bits/stdc++.h>
using namespace std;
int w[21][21][21];
int getW(int a, int b, int c) {
// a, b, c 범위 체크
if (a <= 0 || b <= 0 || c <= 0) return 1;
if (a > 20 || b > 20 || c > 20) return getW(20, 20, 20);
// 이미 계산된 a b c인지 확인
// 계산된 게 맞다면 바로 저장된 값 리턴
if (w[a][b][c] != -1) return w[a][b][c];
// 아니라면 점화식 수행
if (a < b && b < c) return w[a][b][c] = getW(a, b, c - 1) + getW(a, b - 1, c - 1) - getW(a, b - 1, c);
else return w[a][b][c] = getW(a - 1, b, c) + getW(a - 1, b - 1, c) + getW(a - 1, b, c - 1) - getW(a - 1, b - 1, c - 1);
return -1;
}
int main() {
ios::ios_base::sync_with_stdio(false);
cin.tie(nullptr);
cout.tie(nullptr);
// 배열 안에 모든 값 -1로 초기화, for문을 사용하는 것보다 빠름
memset(w, -1, sizeof(w));
int a, b, c;
while (true) {
cin >> a >> b >> c;
if (a == -1 && b == -1 && c == -1) break;
cout << "w(" << a << ", " << b << ", " << c << ") = " << getW(a, b, c) << '\n';
}
return 0;
}
2. Bottom-Up
점화식이 있을 때 Bottom-Up방식 구현은 너무나도 쉽다.그냥 for문을 통해 구현해서 배열w를 채우자 !
#include <bits/stdc++.h>
using namespace std;
int w[21][21][21];
int main() {
ios::ios_base::sync_with_stdio(false);
cin.tie(nullptr);
cout.tie(nullptr);
for (int a = 0; a < 21; a++)
for (int b = 0; b < 21; b++)
for (int c = 0; c < 21; c++) {
// a, b, c가 20을 넘는 경우는 없기 때문에, 0보다 작거나 같은 경우만 신경쓰자.
if (a <= 0 || b <= 0 || c <= 0){
w[a][b][c] = 1;
}
else if (a < b && b < c){
w[a][b][c] = w[a][b][c - 1] + w[a][b - 1][c - 1] - w[a][b - 1][c];
}
else {
w[a][b][c] = w[a - 1][b][c] + w[a - 1][b - 1][c] + w[a - 1][b][c - 1] - w[a - 1][b - 1][c - 1];
}
}
int a, b, c, result;
while (true) {
cin >> a >> b >> c;
if (a == -1 && b == -1 && c == -1) break;
if (a <= 0 || b <= 0 || c <= 0) result = 1;
else if (a > 20 || b > 20 || c > 20) result = w[20][20][20];
else result = w[a][b][c];
cout << "w(" << a << ", " << b << ", " << c << ") = " << result << '\n';
}
return 0;
}
DP문제 풀이의 감을 잡으면 DP만큼 쉬운 문제가 없다고들 하는데, 나는 감이 아직도 안온다;;
앞으로 단순 점화식만 소개하는 것이 아니라, 어떻게 그 점화식을 떠올리게 되었는지도 적을 예정이니 재미삼아 읽어보는 것도 좋을 것 같다.
DP를 구현하는 방법은 크게 두 가지가 있다. 재귀를 이용한 Top-Down 방식과 for문을 이용한 Bottom-Up방식이 있다.자세한 내용은 동적 계획법1의 첫번째 문제인 피보나치 문제에서 설명해보겠다.
아 ! 한가지 Tip을 드리자면, 가끔 문제를 풀 때 \(1,000,000,009\)같이 매우 큰 소수로 나눈 나머지를 답으로 내라는 문제들이 있다.이럴 땐, 꼭!!!! DP나 Memorization쪽을 고려해보자. 왜냐하면, 저렇게 큰 소수로 나눈 나머지가 답으로 나오는 문제들은 적어도 저 소수보다 많은 경우가 나온다는 말인데... 그 경우를 하나하나 세면 무조건 시간초과일 것이다.
