[백준] 2193.cpp : 이친수

www.acmicpc.net/problem/2193

2193번: 이친수

---

• 맨 앞 자리 숫자는 반드시 1부터 시작해야 하기 때문에, 한자릿수 1부터 시작해서 뒤에 숫자를 붙여나갈 수 있다.
• 앞선 숫자가 1로 끝났다면 뒤의 숫자는 1이 올 수 없기 때문에, 반드시 0 이 붙어야 한다.
• 앞선 숫자가 0으로 끝났다면 뒤의 숫자는 1과 0 둘 다 올 수 있다.
• n번째 이친수의 갯수 = (n-1 번째 이친수 중 1로 끝난 갯수) + (n-1 번째 이친수 중 0 으로 끝난 갯수) * 2 개가 된다.
• 1로 끝난 이친수와 0으로 끝난 이친수의 갯수를 따로 DP 배열로 저장해놓고 n 번째 갯수를 구해나간다.

---

#include <iostream>

using namespace std;

int n;

pair<unsigned long,unsigned long> nums[91];     // <끝이 0 으로 끝나는 숫자, 끝이 1 로 끝나는 숫자>

int main(void)
{
    cin >> n;
    nums[1] = {0, 1};                           // 1자리 숫자는 1 밖에 없기 때문에 <0,1> 로 시작
    
    for(int i = 2 ; i <= n ; i++)               // 2자리 숫자부터 n 자리 숫자까지
    {
        nums[i] = {nums[i-1].first + nums[i-1].second, nums[i-1].first};    // i 번째 자리에서 가능한 값은
    }                                                                       // 0 으로 끝나는 값은 i-1 번째에서 뭐가 오든 상관없지만
                                                                            // 1 로 끝나는 값은 i-1 번째에서 반드시 0으로 끝나야 한다
    cout << nums[n].first + nums[n].second << endl; // 가능한 n 자리 숫자의 갯수
}

---

• 2등 소스코드 참고 : www.acmicpc.net/source/18533239
• 간단하게 피보나치 수열처럼 풀 수 있다.
• 첫자리는 반드시 1, 두자리까지는 반드시 10 이 나와야 한다.
• 세번째 자리부터는 10 에 한자리 추가, 네번째는 10 에 두자리 추가, n 번째는 10 에 n-2 자리를 추가한다.
• 다만 n-2 자리를 채울 때는 0 부터 시작해도 되기 때문에 해당 갯수를 찾아야 하지만, n-1 자리의 맨 앞 1 을 뺀 값과 동일하다.
• 따라서 ans[n] = ans[n-1] + ans[n-2] 가 된다.

---

#include <iostream>

int N;
long long a[91] = {0, 1};

int main()
{
    scanf("%d", &N);
    for(int i = 2 ; i <= N ; i++)
    {
        a[i] = a[i-1] + a[i-2];
    }
    printf("%lld", a[N]);
}