이 문제는 dp를 이용하는 문제였다. 노트에 끄적이면서 계산해보면 대충 피보나치 수열의 규칙이 숨겨져있는 문제임을 알 수 있는데, 현재 내 코드의 문제를 리뷰해보자면,
int result = 1;
for (int i = 1; i <= vipNum; i++)
result *= cache[VIP[i] - VIP[i - 1] - 1];
return result *= cache[N - VIP[vipNum]];
이건 다른 분의 코드를 일부 가져온 것인데, 핵심 알고리즘이 훨씬 단순명료함을 알 수 있다. 급하게 풀 때는 이런 식을 생각하기는 사실 쉽지 않지만, 계속해서 연습해야겠다.
아래는 나의 코드이다.
#include <iostream>
#include <vector>
using namespace std;
int n, m;
int marr[42];
int dp[42] = {0};
vector<int> mvec;
int main() {
cin >> n;
cin >> m;
for (int i = 0; i < m; i++) {
cin >> marr[i];
}
for (int i = 0; i < m; i++) {
int temp = marr[i];
if (i == 0) {
mvec.push_back(temp - 1);
if (m == 1) {
mvec.push_back(n - temp);
}
} else if (i == m - 1) {
if (m != 1) {
mvec.push_back(temp - marr[i - 1] - 1);
}
mvec.push_back(n - temp);
} else {
mvec.push_back(temp - marr[i - 1] - 1);
}
}
dp[0] = 1;
dp[1] = 1;
dp[2] = 2;
long long temp = 1;
for (int i = 3; i < 41; i++) {
dp[i] = dp[i - 1] + dp[i - 2];
}
for (int i = 0; i < mvec.size(); i++) {
// cout << "mvec[i]:" << mvec[i] << endl;
temp = temp * dp[mvec[i]];
}
if (mvec.size() == 0) temp = temp * dp[n];
cout << temp << endl;
return 0;
}