[Algorithm] 이친수

이번 문제는 이친수 이다.

먼저 문제 부터 보자.

위와 같이 시작이 1로 시작하고 1이 두번 연속으로 나타나지 않는 다는 조건이다.

다양한 풀이가 생길 수 있을 꺼라고 생각하지만 나는 다음과 같은 방법으로 풀었다.

사실 이 문제 분류는 DP로 되어있긴 하지만 나는 풀면서 수학 , 그중에서도 수열문제와

같다고 생각하였다.

문제 해결 방법은 다음과 같다.

문제에서 연속된 1이 나오면 안되므로 N자리수에서의 이친수의 갯수는 두가지 종류로 

나누어진다. N-1자리의 이친수에 대하여 끝이 0으로 끝나는 수와 1로 끝나는 수.

각각에 대하여 끝이 0 으로 끝난 다면 N자리에서는 2배만큼의 이친수가 생성되고 , 

끝이 1로 끝난다면 N자리에서는 1배만큼의 이친수가 생성된다.

하지만 더욱 자세하게 들여다 보면 N자리의 이친수 중 끝이 0 으로 끝나는 것은

반드시 N-1자리의 이친수 중 끝이 1로 끝나는 것 + 끝이 0으로 끝나는 것 만큼 이다.

또한 N자리의 이친수 중 끝이 1로 끝나는 것은 반드시 N-1 자리의 이친 수중 끝이 0으로

끝나는 것 만큼이다.

그렇기 때문에 나는 이렇게 정의 하였다. 

각각 bit_0 , bit_1 (0으로 끝나는 이친수의 갯수 ,  1로 끝나는 이친수의 갯수) 을 설정하고 

수식을 세우면 다음과 같다.

결과 값은 두개의 경우의 수를 더한 값이 된다 . 

끝 !!

소스코드 :

package algorithm;

import java.io.*;

public class a_2193 {

public static void main(String[] args) throws IOException{

BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

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

long bit_0 = 0;

long bit_1 = 1;

long temp = 0;

for (int i = 1;i<N;i++){

temp = bit_0;

bit_0 = bit_0 + bit_1;

bit_1 = temp;

}

System.out.println(bit_0+bit_1);

}

}