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++
복사