JArchive 프로그래밍 일기

문제

이친수 백준 2193번

리뷰

0 뒤에는 0, 1 둘 다 올 수 있고, 1 뒤에는 반드시 0이 와야한다. (1이 연속되면 안되는 규칙 때문)

앞서 풀었던 쉬운계단수문제 와 비슷한 아이디어로 풀었다.

N자리 수의 마지막 자리 숫자가 0인 경우, N자리 수의 마지막 자리 숫자가 1인 경우의 규칙을 찾는 것이다.

1자리, 2자리 , ... 7자리 까지 이친수 경우를 써보면 발견할 수 있었다.

1자리 -> 1 arr[1] [1] = 1

2자리 -> 10 arr[2] [0] = 1

3자리 -> arr[3] [0] = 1 , arr[3] [1] = 1 100, 101

4자리 -> arr[4] [0] = 2, arr[4] [1] = 1 1000, 1001, 1010

5 자리 -> arr[5] [0] = 3, arr[5] [1] = 2 10010, 10001, 10000, 10101, 10100

6자리 -> arr[6] [0] = 5, arr[6] [1] =3

아래와 같은 점화식을 만들 수 있다.

    arr[i][0] = arr[i-1][0] + arr[i-2][0];
    arr[i][1] = arr[i-1][0];

코드

#include <stdio.h>
using namespace std;

 // 이친수 (2193)

long long arr[91][2];

int main(void){

    int n = 0;
    int i = 0;

    scanf("%d", &n);

    arr[1][1] = 1;

    arr[2][0] = 1;

    arr[3][0] = 1;
    arr[3][1] = 1;

    for(i = 4; i <= n; i++){
        arr[i][0] = arr[i-1][0] + arr[i-2][0];
        arr[i][1] = arr[i-1][0];
    }

    printf("%lld", arr[n][0] + arr[n][1]); // 답 출력할 때 long long 자료형 

    return 0;
}