백준 2193번 이친수 (C++)

문제 링크 : www.acmicpc.net/problem/2193

2193번: 이친수

이 문제는 백준 15990번 1,2,3 더하기 5와 동일한 유형의 문제다.

n길이의 이친수를 만들기 위해서는 n-1번째 숫자가 0인지 1인지를 구분하면 된다. 

 

문제 풀이는 다음과 같다.

1. 이차원 배열[91][2]를 선언한다.

2. 문제에 주어진 예시 값들을 토대로 1번째 길이의 숫자까지 초기화 해준다.

나는 편의상 문제에서 주어진 4번째 길이까지 배열들의 값을 초기화해줬다.

3. n-1번째 숫자가 0일 경우, 다음 숫자는 0이와도 1이와도 상관없다. 때문에 arr[n-1][0]과 arr[n-1][1]을 더해주면 된다.

4. n-1번째 숫자가 1일 경우, 다음 숫자는 오로지 0만 올 수 있다. 때문에 arr[n-1][1]만을 더해주면 된다.

5. 이렇게 구해준 3번과 4번을 더해주면 arr[n][0], arr[n][1]의 합을 구할 수 있고, 이것이 정답이 된다.

 

#include <iostream>
using namespace std;

long long arr[91][2];

long long Calculation(int n){
    long long ans = 0;
    arr[1][0] = 0, arr[1][1] = 1;
    arr[2][0] = 1, arr[2][1] = 0;
    arr[3][0] = 1, arr[3][1] = 1;
    arr[4][0] = 2, arr[4][1] = 1;
    for(int i=5; i<=n; i++){
        arr[i][0] = arr[i-1][0] + arr[i-1][1];
        arr[i][1] = arr[i-1][0];
    }
    ans = arr[n][0] + arr[n][1];
    return ans;
}

int main() {
    ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
    int n = 0;
    cin >> n;
    cout << Calculation(n) << "\n";
    return 0;
}

한 번 틀렸는데, 무턱대고 문제를 읽다가 문제에서 언급한 arr[4][0]의 예시를 한 개만 적어줘서 그렇다.

arr[4][0]으로는 1000, 1010이 올 수 있으므로 2이다.