[백준] 2193 이친수 [java]

문제

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

intro..

완전탐색으로 풀면 솔직히 쉬울 것 같았다. 탐색하고 조건에 맞는 것들의 수를 세면 되기 때문.
하지만, dp 연습을 하기 위해 이 문제를 선택했고, dp로 문제를 풀었다.

풀이

맨 앞은 1로 시작해야 하고, 1이 연속으로 나오면 안된다. 대충 나열 해보면
1
10
100 101
1000 1001 1010

잘 생각해보면, 네 자릿수일 때, 앞에 10은 고정이고 뒤에는 두 자릿수가 올 수 있다.

네 자릿수의 10 뒤에 올 수 있는 수는 10, 00, 01이다. 1로 시작하는 수는 10이고, 0으로 시작하는 수는 00, 01이다.

다섯 자릿수도 같다.
점화식 : dp[i] = dp[i - 1] + dp[i - 2]

전체 코드

import java.util.Scanner;

// 1로 시작, 1이 두번 연속 ㄴㄴ
public class Boj2193 {
//public class Main {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int n = scanner.nextInt();
        long[] dp = new long[n + 1];

        dp[1] = 1;
        if(dp.length > 2){
            dp[2] = 1;          // 10
        }

        // i-2번째는 1로 시작하는거, i-1번째는 0으로 시작하는거
        for(int i = 3; i <= n; i++){
            dp[i] = dp[i - 1] + dp[i - 2];
        }

        System.out.println(dp[n]);
    }
}