[Baekjoon] 백준 2193_이친수 (Java)

2193번: 이친수

 

문제 풀이

"이친수"의 조건이 되려면 아래와 같다.

1. 이진수 중에
2. 1로 시작하는 수
3. 1이 두 번 연속 있으면 안 됨

이 조건에 맞는 경우를 각 자리 별로 찾아봤을 때 일정한 규칙을 찾을 수 있었다. 이전 자리 수에서 찾은 이친수를 그대로 가져와 이용할 수 있는데, 해당 수의 끝 자리가 1로 끝나면 연속으로 1이 올 수 없으니 0만 붙일 수 있다. 반대로 0으로 끝나는 수면 0과 1을 모두 붙일 수 있다. 따라서 자릿수가 4인 이친수를 구하는 경우엔 자리수가 3인 이친수에서 0으로 끝나는 100에 0과 1을 붙인 1000과 1001을 만들 수 있고, 101에는 0만 붙여 1010을 만들 수 있다.

그렇게 구한 경우의 수는 1, 1, 2, 3, 5, 8, 13, ... 이런 식으로 증가하기 때문에 점화식은 아래와 같이 구할 수 있다.

dp[i] = dp[i-1] + dp[i-2]

 

 

소스코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int N = Integer.parseInt(br.readLine());

        if(N == 1 || N == 2){
            System.out.println(1);
            return;
        }

        long[] dp = new long[N+1];
        dp[1] = 1;
        dp[2] = 1;
        for(int i = 3 ; i <= N ; i++){
            dp[i] = dp[i-1] + dp[i-2];
        }
        System.out.println(dp[N]);
    }
}