[백준]2193. 이친수

[문제]

 

www.acmicpc.net/problem/2193

2193번: 이친수

 

[풀이]

 

N이 1인 경우부터 모든 경우의 수를 구하다 보면 규칙을 금방 발견할 수 있다.

규칙을 통해 아래와 같이 점화식을 세워서 DP를 사용해 풀었다.

        DP[i] = DP[i-1]+DP[i-2];

 

[코드]

 

시간 : 0ms

 

#include <iostream>
#define MAX 90

using namespace std;

long long DP[MAX]={0,};
int N;

int main(void)
{
    cin >> N;
    DP[1] = 1;
    DP[2] = 1;
    
    for(int i=3;i<=N;i++)
    {
        DP[i] = DP[i-1]+DP[i-2];
    }
    cout << DP[N];
    return 0;
    
}