이전문제와 점화식만 다르지만 점화식을 변형할 수 있는 문제다. 이번에도 마찬가지로 Top-down / Bottom-up 두 가지 방식을 모두 풀이하겠다.
Top-down
삼각형의 두 변이 나란해지는 인덱스 격차(Offset)는 5다. 따라서 5번째 이전 항목들은 모두 기저 사례 취급한다. 현재 인덱스가 5이상인 경우는 의 점화식이 적용된다. 삼각형 변의 길이가 모두 동일할 때는 인덱스가 차이가 2여도 변이 평행해지기 때문에 이런 예외 로직을 구현하기보단 기저 사례 취급해서 코드를 작성하는게 더 편리하다.
#include <iostream>
#include <vector>
using namespace std;
using ull = long long;
vector<ull> dp;
ull r(int n) {
if (dp[n] != -1) return dp[n];
return dp[n] = r(n - 1) + r(n - 5);
}
int main() {
int tc; cin >> tc;
while (tc--) {
int n; cin >> n; dp = vector<ull>(n + 1 > 5 + 1 ? n + 1 : 5 + 1, -1);
dp[1] = 1;
dp[2] = 1;
dp[3] = 1;
dp[4] = 2;
dp[5] = 2; // 미리 메모이제이션 배열에 기저 사례 입력
cout << r(n) << "\n";
}
return 0;
}Botton-up
사실 점화식이 하나 더 있는데 이다. 삼각형은 모두 정삼각형이고 기술한 2개의 삼각형의 변의 합으로 현재 삼각형의 변이 만들어지는 것을 유추할 수 있다. 이처럼 같은 문제라도 찾은 규칙이나 발견한 직관에 따라 여러 점화식을 작성할 수 있다.
#include <iostream>
#include <vector>
using namespace std;
using ull = long long;
int main() {
vector<ull> dp(101);
dp[1] = 1; dp[2] = 1; dp[3] = 1;
for(int i=4;i<=100;i++) {
dp[i] = dp[i - 2] + dp[i - 3];
}
int tc; cin >> tc;
while (tc--) {
int n; cin >> n; cout << dp[n] << "\n";
}
return 0;
}