[백준] 이친수 (JAVA)

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

 

 

0과 1로만 이루어진 숫자를 이진수라고 부르죠?

여기 특별한 규칙을 가진 이진수가 있습니다. 이친수라고 부르는데요

그 규칙은

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

이러한 규칙을 갖고 있습니다.

즉, 1, 10, 100, 101, 1000, ...

이런식으로 증가하겠죠.

여기에서 양의 정수 n을 입력했을 때, n자리의 이친수의 개수를 출력하면 됩니다.

 

저는 이 문제를 보자마자 1자리 이친수, 2자리 이친수... 이렇게 각 자릿수의 이친수를 적어봤습니다.

1자리(1개) - 1

2자리(1개) - 10

3자리(2개) - 100, 101

4자리(3개) - 1000, 1001, 1010

5자리(5개) - 10000, 10001, 10010, 10100, 10101

 

이런식으로 각 자릿수마다 이친수와 개수를 적어봤는데요

특별한 규칙이 보이지 않습니까?

3자리 이친수의 개수 = 1자리의 이친수, 2자리의 이친수의 개수의 합

4자리 이친수의 개수 = 2자리의 이친수, 3자리의 이친수의 개수의 합

5자리 이친수의 개수 = 3자리의 이친수, 4자리의 이친수의 개수의 합

 

이런 피보나치 수열과 같은 규칙을 가지게 됩니다.

그래서 저는 피보나치 수열 알고리즘을 활용해서 문제를 풀어보기로 했습니다.

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

// 백준 이친수
// 기존에 이진수는 0과 1로만 이루어진 숫자
// 이친수의 조건
// 1. 0으로 시작하지 않는다
// 2. 1이 연속으로 나타나지 않는다
// 양의 정수를 n을 입력했을 때 n자리 이친수의 개수 출력
public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int num = Integer.parseInt(br.readLine());
        // 개수 저장 배열
        long[] arr = new long[num + 2];

        // 피보나치네요
        arr[0] = 0;
        // 1
        arr[1] = 1;
        // 10
        // 100, 101
        // 1000, 1001, 1010
        // 10000, 10001, 10010, 10100, 10101
        for (int i = 2; i < num + 1; i++) {
            arr[i] = arr[i - 1] + arr[i - 2];
        }
        System.out.println(arr[num]);
    }
}

 

숫자가 너무 커지면 에러가 발생하므로 long을 이용해 정수형 배열을 선언해주었습니다.

피보나치 수열 하면 재귀함수를 사용할 수도 있었지만, 메모리와 시간을 너무 많이 사용하는 관계로 사용하지 않았습니다.

 

노래 추천 : Mac Miller - My Favorite Part (feat. Ariana Grande)