Search
Duplicate

파도반 수열

주차
11주차
문제번호
9461
언어
티어
실버
유형
DP
nj_Blog
nj_상태
이해도
풀이
사람
이해도 2
13 more properties

Memo

접근 방법
위의 설명을 보자마자 규칙이 너무 명확히 보였습니다. dp[n] = dp[n - 2] + dp[n - 3]을 점화식으로 둡니다.
최댓값 고려
N이 100이 들어왔을 때의 결과값이 int형 범위를 초과하기 때문에 long long 으로 타입을 변경했습니다. 이때 위의 점화식의 문제인줄 알고 dp[n] = dp[n - 5] + dp[n - 1]로 점화식을 변경했습니다.
저 점화식은 실제로 어떻게해서 나오는가
문제를 풀고 다음날인 2월 24일. @suhshin과 @jseo와 얘기를 나눈 결과
dp[n] = dp[n - 1] + dp[n - 5]인 경우에는 삼각형의 빗변에 인접해 있는 두 삼각형 빗변들의 길이 합이고,
dp[n] = dp[n - 2] + dp[n - 3]인 경우에는 삼각형의 빗변을 평행 사변형으로 확장했을 경우에 두 삼각형 빗변 길이들의 합이 됩니다.
값을 미리 넣어놓은 이유
N의 값이 크지 않고 테스트케이스마다 값이 들어오므로, 미리 배열에 할당해 놓은다음 인덱스 접근하는 방법을 택했습니다.

Code

제출 날짜

@2/23/2021

메모리

2016 KB

시간

0 ms
#include <iostream> #include <vector> #define endl "\n" typedef long long ll; int T, N; std::vector<ll> padovan; void input_faster() { std::ios_base::sync_with_stdio(false); std::cin.tie(0); std::cout.tie(0); } void input() { input_faster(); std::cin >> T; padovan.resize(101); } void logic() { padovan[1] = 1; padovan[2] = 1; padovan[3] = 1; padovan[4] = 2; padovan[5] = 2; for (size_t i = 6 ; i < 101 ; i++) padovan[i] = padovan[i - 5] + padovan[i - 1]; } void print_val() { std::cin >> N; std::cout << padovan[N] << endl; } int main() { input(); logic(); while (T--) print_val(); return (0); }
C++
복사