https://www.acmicpc.net/problem/9461
다른 DP문제에 비해 쉬운 문제라고 생각합니다.
처음 9번째항까지는 일정한 규칙이 없지만 10번째 부터는 규칙이 일정하기 때문에,
조금만 생각하시면 바로 푸실 수 있습니다.
유의할 점은 n이 100일 경우 8 * 10^11의 엄청난 수가 나오기 때문에
long long 타입으로 변수를 맞추고 당연히 출력도 %lld로 해줘야한다는 점입니다.
#include <iostream>
#include <cstdio>
using namespace std;
long long p[101] = { 0,1,1,1,2,2,3,4,5,7 };
int main() {
int test_case,n;
scanf("%d", &test_case);
for (int t = 0; t < test_case; t++) {
scanf("%d", &n);
for (int i = 10; i <= n; i++) {
p[i] = p[i - 1] + p[i - 5];
}
printf("%lld\n", p[n]);
}
}
- 혼잣말
계속 왜맞틀 하다가 다른 사람의 코드를 보고 타입의 문제라는 것을 깨달았다…..
long long.. ㅂㄷㅂㄷ.. 같은 실수를 반복하는구만.. 다음부턴 수가 많이 커지지는 않는지부터 생각해야겠다..