[백준2193번/자바] 이친수

문제

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자리 이친수의 개수를 출력한다.

 

---

 

열심히 dp를 사용해서 풀었고 시간 초과가 떴다...

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.lang.reflect.Array;
import java.util.Arrays;

public class BJ2193 {

    static int result;

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

        int[] arr = new int[n];
        arr[0] = 1;
        result = 0;
        dp(n - 1, 0, arr);
        System.out.println(result);
    }

    static void dp(int n, int cnt, int[] arr) {
        // 종료 조건
        if(n == cnt) {
            result++;
            return;
        }

        // 현재 값이 1이면 다음 수는 0
        if(arr[cnt] == 1) {
            arr[cnt + 1] = 0;
            dp(n, cnt + 1, arr);
        }

        // 현재 값이 0이면 다음 수는 0과 1 모두 올 수 있음
        else {
            for (int i = 0; i < 2; i++) {
                arr[cnt + 1] = i;
                dp(n, cnt + 1, arr);
            }
        }


    }


}

 

3
1 0 0
1 0 1

4
1 0 0 0
1 0 1 0
1 0 0 1

5
1 0 0 0 0
1 0 1 0 1
1 0 1 0 0
1 0 0 1 0
1 0 0 0 1

 

어차피 첫번째 수가 1이듯 두번째 숫자는 0이다.

이부분에 대한 불필요한 연산을 제거하면 되는걸까?

 

그렇다고 유의미하게 시간을 줄여주지 않을거같다. 흠.

 

https://m.blog.naver.com/occidere/220788046159

혼자 해결하고 싶었지만 홀린듯이 읽어버렸다.

규칙이 있을법 할때는 조금더 유심히 들여다보자!

그리고 자료형의 범위를 항상 유의하자!

 

(위 블로그 발췌)

피보나치 수는 분명 전에도 설명했다시피 46항(이 문제에선 47번째)이 되면 2971215073가 되어 int의 범위를 초과하기 때문이다. 

 

 

메모이제이션을 안써서 그런지 또 시간 초과가 났다...

다시 코드 수정...

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

public class BJ2193 {

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

        if(n == 1) {
            arr[0] = 1;
        } else if (n == 2) {
            arr[1] = 1;
        } else {
            fibo(n - 1, arr);
        }

        System.out.println(arr[n - 1]);
    }

    static long fibo(int n, long[] arr) {
        if(n == 0 || n == 1) {
            return 1;
        } else if (arr[n] != 0) {
            return arr[n];
        } else {
            arr[n] = fibo(n - 1, arr) + fibo(n - 2, arr);
            return arr[n];
        }
    }


}

 

드뎌 정답!