2193. 이친수

1. 해결방법

• Dynamic Programming
• DP[n] : n자리 수 이친수 개수를 의미
• DP[1] = 1
• DP[2] = 1
• DP[3] = 2
• DP[n] = DP[n-1] + DP[n-2]

 

2. Solution

// Dynamic Programming
#include <iostream>

#define MAX 90 + 1
#define endl "\n"

typedef long long ll;
using namespace std;

ll N;
ll DP[MAX];

void Input()
{
    cin >> N;
}

void Initial()
{
    DP[0] = 0;
    DP[1] = 1;
    DP[2] = 1;
}

void Solution()
{

    for (int i = 3; i <= N; i++)
    {
        DP[i] = DP[i - 1] + DP[i - 2];
    }

    cout << DP[N] << endl;
}

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);

    Input();
    Initial();
    Solution();

    return 0;
}

 

3. 알아야 할 개념

• typedef

: 기존에 존재하는 자료형의 이름을 재정의 할 수 있다.

#include <iostream>
#define MAX 90 + 1

// long long 자료형을 ll 로 재정의
typedef long long ll;

using namespace std;

 

• long long 자료형

✔️ 정수 자료형

✔️ 크기 : 8 bytes

✔️ 범위 : –9,223,372,036,854,775,808 ~ 9,223,372,036,854,775,807