[백준/C++] 9461번 파도반 수열
2021. 2. 17. 23:11ㆍ알고리즘/DP
728x90
반응형
문제: www.acmicpc.net/problem/9461
문제풀이
DP문제이다.
문제의 점화식
P[i] = P[i-5] + P[i-1]
주의할 점은 배열을 선언할 때 long long 형으로 선언해주어야 한다는 것이다. 처음 문제를 풀 때 int 형으로 선언하여 9%에서 계속 틀려서 헤매었다.
코드
#include <iostream>
using namespace std;
int main(){
ios::sync_with_stdio(false); cin.tie(nullptr);
int T;
cin>>T;
while(T--){
long long N;
cin>>N;
long long p[101] = {1, 1, 1, 2, 2, 3, 4, 5, 7, 9}; //P[10] 까지는 문제에 명시 되어 있다.
for(int i=10; i<N; i++){
p[i] = p[i-5]+p[i-1]; //점화식
}
cout<<p[N-1]<<"\n"; //0부터 시작했으므로 인덱스에서 1을 빼준다.
}
return 0;
}
결과
728x90
반응형
'알고리즘 > DP' 카테고리의 다른 글
[백준/C++] 11727번 2×n 타일링 2 (0) | 2021.02.17 |
---|---|
[백준/C++] 11726번 2×n 타일링 (0) | 2021.02.17 |
[백준/C++] 1676번 팩토리얼 0의 개수 (0) | 2021.02.13 |
[백준/C++] 1003번 피보나치 함수 (0) | 2021.02.13 |