[백준] 2193 : 이친수 - Java

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

---

• 문제
  

---

• 풀이

알고보면 간단한 피보나치수열 문제이다.

문제의 조건에 따라서 이진수의 시작은 무조건 1이다.

여기서부턴 맨 끝의 수만 보고 몇 개의 수가 파생될지 알 수 있다.

직접 N=5까지 예시를 들어보겠다.
N=1 1
N=2 10
N=3 101 100
N=4 1010 1001 1000
N=5 10101 10100 10010 10001 10000

규칙이 보이는가 ?

이진수의 맨끝수가 0이면 2개의 이진수가 파생되고 1이면 1개만 파생되는것을 확인 할 수 있다.

즉 맨 끝의 수만보고 다음N자리 이진수의 개수를 알 수 있다는 거고 이에 따라 N자리 이진수들의 개수를 나열해보면 아래와 같다.
1 1 2 3 5 8 13 ........

점화식이 d[n] = d[n - 1] + d[n - 2] 인 피보나치수열인 것을 확인할 수 있다.

마지막으로 주의할점은 N의범위가 최대 90이기 때문에 int의 범위는 모자라서 long타입의 배열을 사용해야한다!!

---

• 코드

import java.io.*;

class Main {
	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 + 1];
		arr[0] = arr[1] = 1;
		for (int i = 2; i <= N; i++) {
			arr[i] = arr[i - 1] + arr[i - 2];
		}
		System.out.println(arr[N - 1]);
	}
}