백준 2193번 이친수(java)

[Silver III] 이친수 - 2193

문제 링크

성능 요약

메모리: 14456 KB, 시간: 100 ms

분류

다이나믹 프로그래밍

제출 일자

2024년 9월 9일 20:15:56

문제 설명

0과 1로만 이루어진 수를 이진수라 한다. 이러한 이진수 중 특별한 성질을 갖는 것들이 있는데, 이들을 이친수(pinary number)라 한다. 이친수는 다음의 성질을 만족한다.

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

예를 들면 1, 10, 100, 101, 1000, 1001 등이 이친수가 된다. 하지만 0010101이나 101101은 각각 1, 2번 규칙에 위배되므로 이친수가 아니다.

N(1 ≤ N ≤ 90)이 주어졌을 때, N자리 이친수의 개수를 구하는 프로그램을 작성하시오.

입력

첫째 줄에 N이 주어진다.

출력

첫째 줄에 N자리 이친수의 개수를 출력한다.

풀이

각 자리 수 별로 몇 개의 이친수가 나오는지 한 번 쫙 살펴보자

 

한 자리: 1

두 자리: 10

세 자리: 100, 101

네 자리: 1001, 1000, 1010

다섯 자리: 10010, 10001, 10000, 10100, 10101

 

규칙을 찾아보자, 1이 연속해서 나오면 안 된다.

 

따라서 1 이후엔 0만 올 수 있고, 0 이후엔 1과 0 두 개가 올 수 있다.

 

그러면 0으로 끝나는 경우가 있을 때만 개수가 1개 씩 증가한다는 말이된다.

 

100 이 1001 과 1000으로 나눠지고, 101은 1010 한 가지 밖에 안 되니 말이다.

 

그러면 우리는 0으로 끝나는 이친수의 개수만 찾으면 문제를 해결할 수 있다.

 

0으로 끝나는 이친 수의 개수는 어떻게 찾을까?

 

간단히 생각해보자 0은 어떻게 발생하는가?

 

1로 끝날 때 10으로 0이 하나 발생하고

0으로 끝날 때 00으로 0으로 끝나는 놈이 하나 발생한다.

 

그렇다 자기의 전 항에 있는 이친수의 갯수만큼 0으로 끝나는 이친수가 생긴다.

 

즉, 자기 항의 갯수  + 전 항의 개수  = 다음 항의 개수 라는 점화식을 발견할 수 있다.

 

한 자리: 1

두 자리: 10

세 자리: 100, 101

네 자리: 1001, 1000, 1010

다섯 자리: 10010, 10001, 10000, 10100, 10101

 

ㅇㅇ 맞다.

 

이제 코드를 짜보자

전체 코드

public class Main {
    public static void main(String args[])throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

        int N = Integer.parseInt(br.readLine());

        BigInteger dp[] = new BigInteger[N+2];

        dp[0] = BigInteger.valueOf(0);
        dp[1] = BigInteger.valueOf(1);
        dp[2] = BigInteger.valueOf(1);

        for(int  i = 3 ;i<=N;i++){
            dp[i] = dp[i-1].add(dp[i-2]);
        }

        bw.write(dp[N] + "");
        bw.flush();
    }
}