2193번

2193번 - 이친수

완전탐색으로 푼 후 , DP로 전환해서 풀었다.

이 문제도 조심할 것은 int 범위를 넘어가서 long long 으로 해줘야 한다는 사실.

항상 문제를 풀고 최대 범위의 N을 넣어서 확인하는 습관이 필요.

D[N][L] = N자리, 끝 수가 L 인 이친수의 갯수

<정답 코드>

#include<iostream>
#include<string.h>
 
using namespace std;
int ans;
long long D[91][2];
 
long long go(int n,int num)
{
    if (n == 1)
    {
        if (num == 0)
        {
            return 0;
        }
        else if (num == 1)
        {
            return 1;
        }
    }
 
    if (D[n][num] != -1)
    {
        return D[n][num];
    }
 
    if (num == 1)
    {
        D[n][num] = go(n - 1, 0);
    }
    
    if (num == 0)
    {
        D[n][num] = go(n - 1, 0) + go(n - 1, 1);
    }
 
    return D[n][num];
}
 
int main()
{
    int N;
    cin >> N;
    memset(D, -1, sizeof(D));
 
    cout << go(N, 0) + go(N, 1) << endl;
 
    return 0;
}

<시간초과 완전탐색 풀이>

#include<iostream>
#include<string.h>
 
using namespace std;
int ans;
 
void go(int n,int num)
{
    if (n == 1)
    {
        if (num == 0)
        {
            return ;
        }
        else if (num == 1)
        {
            ans += 1;
            return;
        }
    }
 
    if (num == 1)
    {
        go(n - 1, 0);
    }
    
    if (num == 0)
    {
        go(n - 1, 0);
        go(n - 1, 1);
    }
 
    return;
}
 
int main()
{
    int N;
    cin >> N;
 
    go(N, 0);
    go(N, 1);
 
    cout << ans << endl;
 
    return 0;
}