백준 파도반 수열(9461) C++ 풀이
알고리즘 분류 수학 다이나믹 프로그래밍(DP) 문제 해결 아이디어 1, 1, 1, 2, 2, 3, 4, 5, 7, 9 ...로 진행되기 때문에 이 패턴을 잘 보면서 4번째부터 n - 3번째 + n - 2번째를 더해 값이 나오는 것을 알 수 있다. 따라서 1,2,3번째를 미리 1로 세팅 후 dp[n - 3] + dp[n - 2]로 해결한다. 코드 #include using namespace std; long long dp[101]; int main() { dp[0] = 0; dp[1] = 1; dp[2] = 1; dp[3] = 1; int t, n; cin >> t; for (int i = 0; i > n; for (int i = 4; i