BOJ_2193 : 이친수

👉 문제링크

2193번: 이친수

---

---

🔸 문제 분석 🔸

• 자리수 n을 입력받고 만들 수 있는 이친수의 개수를 출력한다.
  • 이친수는 이진수에서 맨 앞에 1이오고, 11처럼 1 두 개가 붙어서 나오는 경우가 없는 수를 말한다.
  • 1부터 경우의 수를 따져보면 다음과 같다.

/*
    n       count       pinary number
    1       1           1
    2       1           10
    3       2           101 100
    4       3           1000 1001 1010
    5       5           10000 10001 10010 10100 10101
    6       8           100000 100001 100010 100100 101000 100101 101001 101010
    90      2880067194370816120
 */

• n이 증가함에 따라 답(count)가 피보나치 수열 형태로 증가함을 알 수 있다.
• 문제의 n의 범위에서 최대값인 90인 경우 count가 int범위를 초과하므로 long형을 써야한다.

🔸 코드 🔸

import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();

        long[] dp = new long[n+1];
        dp[0] = 0;
        dp[1] = 1;

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

🔸 코드 해석 🔸

• n을 입력받고 n+1크기의 long형 배열을 선언한다.
• 초기값으로 인덱스 0에는 0을, 인덱스 1에는 1을 넣는다.
• 인덱스 n까지 피보나치 수열 계산을 반복하고 값을 출력한다.

---

🔸 end 🔸

• 처음엔 감이 안잡혔지만 경우의 수를 따져보니 피보나치 수열이라는 것을 알아차려서 쉽게 풀이할 수 있었다.
• dp 배열의 자료형을 int로해서 1회 틀렸다.
  • int로 선언했을때의 코드에서 n을 90으로 입력해봤으면 int를 벗어난다는 것을 알 수 있었는데 안일했던 것 같다.