[알고리즘] 이친수

구현 방식

• 아래의 사진과 같이 i 번째 자리는 i - 1 번째에서 나올 수 있는 이진 수에서 0 또는 1 을 끝에 붙여서 만들 수 있다.

• 다만 맨 끝자리가 1로 끝난 경우에는 끝에 0 만 붙일 수 있고, 0 으로 끝났을 때는 0 과 1 둘다 올 수 있다.
• 즉, i - 1 번째에서 0 으로 끝난 이진수의 개수를 a 개 1 로 끝난 이진수의 개수를 b개라고 했을 때
• i 번째에서 0으로 끝난 이진수의 개수는 a + b 개, 1로 끝난 이진수의 개수는 a 개 이다.
• 이를 점화식으로 나타내면 아래와 같다.

acc[i].endZERO = acc[i-1].endZERO + acc[i-1].endONE
acc[i].endONE = acc[i-1].endZERO

코드

• 코드는 아래와 같다. 튜플을 이용해서 first 에는 0으로 끝나는 이진수의 개수를, second 에는 1로 끝나는 이진수의 개수를 담았다.

long long DP(int N)
{
    // first : 0으로 끝나는 이진수의 개수 , second : 1로 끝나는 이진수의 개수
    vector<pair<long long, long long>> acc = vector<pair<long long, long long>>(N + 1);
    acc[1] = { 0 , 1 }; // 1 한개

    for (int i = 2; i <= N; i++)
    {
        acc[i] = { acc[i - 1].first + acc[i - 1].second, acc[i - 1].first };
    }

    return acc[N].first + acc[N].second;
}