9461번 : 파도반 수 [C++]

문제 링크

성공 여부(걸린 시간): 성공(10분)

아이디어

나선으로 삼각형을 계속 추가해서 N번째 추가했을 때의 해당 추가한 삼각형의 한 변의 길이를 구하는 것이다.
그래서 나선형으로 하다보니 아무래도 특정 삼각형 2개의 각 변의 길이를 합한 것이 새로운 삼각형의 한 변의 길이가 된다.
전형적인 DP기본 문제

 

그래서 내가 작성한 점화식은

f(n) = f(n-1)+f(n-5) (x>5일때)

5까지의 변의 길이는 직접 추가해준다.

1, 1, 1, 2, 2

 

그 다음부터는 직전의 삼각형의 한 변의 길이 + 5번째 전의 삼각형의 한변의 길이가 됨으로 갱신해주면 끝이다.

 

‼️‼️‼️
그러나 여기서 간과한점
자료형
본인은 vector의 내부 인자 타입을 int로 정의했는데 제출하니 바로 틀렸다.

 

왜냐면 N이 최대 100인데 f(N)=8800억 정도 된다.
그럼 overflow 발생...

그래서 long long int로 바꾸어 줬더니 성공했다.
자료형 조심

풀이 코드

#include<iostream>
#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 int> v(101, 0);
    v[1] = v[2] = v[3] = 1;
    v[4] = v[5] = 2;
    for (int i = 6; i < 101; i++) {
        v[i] = v[i - 1] + v[i - 5];
    }
    while (T-- != 0) {
        int N;
        cin >> N;
        cout<<v[N]<<"\n";
    }
    return 0;
}