[C++] BOJ 2193번: 이친수

문제 링크

문제 풀이

이 문제를 풀 때에 애를 많이 먹었다. 결론부터 말하면 풀이가 문제가 아니라 타입이 문제였다. int형이 아닌 long long형을 써야 문제가 풀릴 거라 생각을 못했는데, 아마도 계산한 값이 엄청 큰 값이 나오는 모양이다.

 

또 질문 게시판을 보며 알게 되었는데 피보나치 수열 문제이기 때문에 피보나치 문제를 풀 때에 사용한 풀이로 풀 수도 있다고 한다.

코드

#include <bits/stdc++.h>

using namespace std;

int N;
long long calculated[93][2];

void calculate(int num)
{
    if (num > N)
        return;
    if (num == 1)
    {
        calculated[1][0] = 0;
        calculated[1][1] = 1;
    }
    else
    {
        calculated[num][1] = calculated[num - 1][0];
        calculated[num][0] = calculated[num - 1][0] + calculated[num - 1][1];
    }
    calculate(num + 1);
}

int main(void)
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    cin >> N;

    calculate(1);

    long long result = calculated[N][0] + calculated[N][1];

    cout << result << '\n';

    return 0;
}