문제
코드
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
int n,a;
ll dp[104];
int main(){
ios_base::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);
cin >> n;
while(n--){
cin >> a;
dp[0] = dp[1] = dp[2] = 1;
dp[3] = dp[4] = 2;
for(int i = 5; i < a; i++){
dp[i] = dp[i-1] + dp[i-5];
}
cout << dp[a-1] << '\n';
}
}풀이
우선 이런 문제가 나오면 일단 몇 번까지는 쭉 써본다.
쓰다보면 뭔가 더해가는 느낌을 받는데 이 한 케이스의 경우가 전체의 경우도 메꿀 수 있는 식이 나온다면 그걸로 코드를 짜면 됐다.
사실 문제에 그림이 나와 있어서 생각해내기가 쉬운 감도 있었다.
결과
후기
오랜만에 몇 분 안걸린 문제가 나와서 행복하다...
DP 문제는 DP임과 점화식을 알아낸다면 행복하게 풀 수 있을듯 하다.
:)