[백준 2193] 이친수

• https://www.acmicpc.net/problem/2193

이진수 10이 존재할때 1을 1번째 자리 수, 0을 2번째 자리수와 같이 표현할 수 있다.

n번째 자리수가 0이라면 n-1번째 자리수는 0또는 1이고, n번째 자리수가 1이라면 n-1번째 자리수는 0이다.

즉 n번째 자리수가 0일 경우의 수는 n-1번째 자리수가 0일 경우의 수와 1일 경우의 수의 합이고

n번째 자리수가 1일 경우의 수는 n-1번째 자리수가 0일 경우의 수와 같다.

점화식

arr[n][m] : n번째 자리수가 m일 경우의 수

arr[0][0] = 0

arr[0][1] = 1

arr[n][0] = arr[n-1][0] + arr[n-1][1]

arr[n][1] = arr[n-1][0]

C++ code

길이 N=90인 이친수는 2,880,067,194,370,816,120개 존재할 수 있이므로 이 값을 저장할 수 있는 변수를 할당해야한다.

데이터 형식 범위 https://docs.microsoft.com/ko-kr/cpp/cpp/data-type-ranges?view=vs-2017

#include <iostream>
using namespace std;
int main(){
    int n;
    cin >> n;
    unsigned long long arr[2][2];
    arr[0][0] = 0;
    arr[0][1] = 1;
    int k = 0;
    for(int i = 1; i < n; i++){
        k = !k;
        arr[k][0] = arr[!k][0] + arr[!k][1];
        arr[k][1] = arr[!k][0];
    }
    cout << arr[k][0] + arr[k][1];
    return 0;
}

•