[BOJ] 백준 2193 - 이친수 (자바)

1자리 수 일때는 1 만 올 수 있다. (1개)

2자리 수 일때는 10 만 올 수 있다. (1개)

3자리 수 일때는 101, 100 이 올 수 있다. (2개)

4자리 수 일때는 1010, 1000, 1001 이 올 수 있다. (3개)

5자리 수 일때는 10100, 10101, 10000, 10001, 10010 이 올 수 있다. (5개)

6자리 수 일때는 101000, 101001, 101010, 100000, 100001, 100010, 100100, 100101 이 올 수 있다. (8개)

어느 정도 규칙이 보이지 않는가? 1 - 1 - 2- 3- 5- 8 - ???

안 보인다면 7자리 수일떄도 해보겠다.

1010000, 1010001, 1010010, 1010100, 1010101, 1000000, 1000001, 1000010, 1000100, 1000101, 1001000, 1001001, 1001010 (13개)

이정도면 보였으리라 생각한다. 피보나치의 규칙을 갖고 있다.

피보나치의 규칙을 이용해서 문제를 풀면 끝!

사실 이문제는 끝자리가 0으로 끝나는 dp[N][0], 1로 끝나는 dp[N][1] 로 푸는게 맞다.

앞의 수가 0일때는 0,1이 둘다 올수 있고 앞의수가 1일때는 0밖에 못오니깐..

아무튼 쉬운 경로로 풀면 되긴 하지만, 좀 더 직관적으로 보이는 뒤의 방법을 이용하는 것이 좋아보인다.

import java.io.FileInputStream;
import java.util.*;
public class Main {
    public static void main(String args[]) throws Exception {
        // Scanner sc = new Scanner(System.in);
        Scanner sc = new Scanner(new FileInputStream("input.txt"));
        int N = sc.nextInt();
        int[] arr = new int[N];
        if (N == 1) {
            arr[0] = 1;
        } else if (N == 2) {
            arr[1] = 1;
        } else {
            arr[0] = 1;
            arr[1] = 1;
            for (int i = 2; i < N; i++) {
                arr[i] = arr[i - 1] + arr[i - 2];
            }
        }
        System.out.println(arr[N-1]);
    }
}