https://www.acmicpc.net/problem/9461
문제
> 오른쪽 그림과 같이 삼각형이 나선 모양으로 놓여져 있다.
> 첫 삼각형은 정삼각형으로 변의 길이는 1이다.
> 그 다음에는 다음과 같은 과정으로 정삼각형을 계속 추가한다.
> 나선에서 가장 긴 변의 길이를 k라 했을 때, 그 변에 길이가 k인 정삼각형을 추가한다.
> 파도반 수열 P(N)은 나선에 있는 정삼각형의 변의 길이이다.
> P(1)부터 P(10)까지 첫 10개 숫자는 1, 1, 1, 2, 2, 3, 4, 5, 7, 9이다.
> N이 주어졌을 때, P(N)을 구하는 프로그램을 작성하시오.
접근
규칙을 구해보면 p(1)과 p(2)를 더하면 p(4)가 나온다. 1+1 = 2, p(2)와 p(3)를 더하면 p(5)가 나온다. 1+1 = 2 p(3)와 p(4)를 더하면 p(6)이 나온다.
따라서 dp(N)은 dp(n-2)+dp(n-3)이다.
문제해결
> 규칙을 사용하려면 최소 dp(1)부터 시작하므로 dp에 들어갈 N이 최소 4는 되어야 한다.
그래서 dp(3)까진 문제에 주어진 입력을 사용한다.
> dp(4)부터 규칙을 적용해 구한다. dp(n) = dp(n-2) + dp(n-3)을 수식으로 입력받은 n까지 계산해 출력한다.코드
#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
int main()
{
ios::sync_with_stdio(false);
cin.tie(nullptr);
cout.tie(nullptr);
int T;
cin >> T;
vector<long long> dp(101);
dp[1] = 1;
dp[2] = 1;
dp[3] = 1;
for (int i = 4; i <= 100; i++) dp[i] = dp[i - 2] + dp[i - 3];
while (T--)
{
int N;
cin >> N;
cout << dp[N] << '\n';
}
}후기
while문안에 vector선언과 dp값을 구해주는 반복문을 넣어 너무 많은 연산이 일어나 틀렸다.
문제에서 N이 100이하라고 헀으므로 미리 dp(100)까지 구하고 while문에선 테스트케이스의 입력에 대한 dp값만처리해주면 된다. 이를 놓쳤다.
