[백준저지] 2193번 : 이친수

www.acmicpc.net/problem/2193

2193번: 이친수

1. 문제 

이친수는 다음의 성질을 만족한다.

1. 이친수는 0으로 시작하지 않는다.
2. 이친수에서는 1이 두 번 연속으로 나타나지 않는다. 즉, 11을 부분 문자열로 갖지 않는다.

입)

3

 

출)

2

 

2. 풀이

import java.util.*;

public class Main {
    public static void main(String args[]) {
        Scanner sc = new Scanner(System.in);
        int N = sc.nextInt();
        long[][] D = new long[91][2];
        D[1][0] = 0;
        D[1][1] = 1;
        D[2][0] = 1;
        D[2][1] = 0;
        for (int i = 3; i <= 90; i++) {
            D[i][0] = D[i-1][1] + D[i-1][0];
            D[i][1] = D[i-1][0];
        }
        System.out.println(D[N][0] + D[N][1]);
    }
}

D[i][j] -> i 자리 이친수 중에 j로 끝나는 것의 개수

D[i][0] = D[i-1][1] + D[i-1][0]

D[i][1] = D[i-1][0]

D[1][0] = 0

D[1][1] = 1

점화식을 세우고, 초기값을 설정 후 풀면 됨