[백준 2193번 이친수 / C++]

www.acmicpc.net/problem/2193

2193번: 이친수

처음 문제를 접했을 때.. 백트래킹부터 생각이났고! ㅎㅅㅎ 백트래킹으로 문제를 접근하였다..허허

결과는 시간초과였고 다시 문제를 풀어보는 수 밖에 없었다.

 

그렇다면 각 자리수에 따라 조건에 맞는 수의 개수에서의 규칙을 찾은 후 디피로 풀어보는 수 밖에 없었다ㅠ

 

처음 dp[1], dp[2]은 1로 채워주었고,,!나머지는 dp[n]=dp[n-1]+dp[n-2]로 배열을 채워주어면 완성시킬 수 있었다!

 

#include <iostream>
using namespace std;
long long dp[91];
void func(int n)
{
    for (int i = 3; i <= n; i++)
        dp[i] = dp[i - 2] + dp[i - 1];
}
int main()
{
    int N;
    cin >> N;
    dp[1] = 1;
    dp[2] = 1;
    func(N);
    cout << dp[N] << "\n";
    return 0;
}