백준 2193번

이친수

문제

0과 1로만 이루어진 수를 이진수라 한다. 이러한 이진수 중 특별한 성질을 갖는 것들이 있는데, 이들을 이친수(pinary number)라 한다. 이친수는 다음의 성질을 만족한다.

이친수는 0으로 시작하지 않는다.
이친수에서는 1이 두 번 연속으로 나타나지 않는다. 즉, 11을 부분 문자열로 갖지 않는다.
예를 들면 1, 10, 100, 101, 1000, 1001 등이 이친수가 된다. 하지만 0010101이나 101101은 각각 1, 2번 규칙에 위배되므로 이친수가 아니다.

N(1 ≤ N ≤ 90)이 주어졌을 때, N자리 이친수의 개수를 구하는 프로그램을 작성하시오.

입력

첫째 줄에 N이 주어진다.

출력

첫째 줄에 N자리 이친수의 개수를 출력한다.

예제

알고리즘 분류

• 다이나믹 프로그래밍

코드

import java.io.*;

public class Main {
	public static long dp[];
	
	public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        
        int N = Integer.parseInt(br.readLine());
        dp = new long[N+1];

        
        System.out.println(Func(N));
	}
	
	public static long Func(int N) {
		if(N == 0)
			return 0;
		
		else if(N == 1)
			return 1;
		
		else if(dp[N] != 0)
			return dp[N];
		
		else
			dp[N] = Func(N-1) + Func(N-2);
		
		return dp[N];
	}
}

풀이

규칙만 발견하면 되는 문제다.

2진수는 0과 1로만 이루어진 수다.
1) N 자리에 오는 수가 0일때
... 0or1 , 0
이므로 N번째 경우는 0으로 확정되었으니 이 경우에 경우의 수는
dp[N-1]라고 할 수 있다. (N-1번째 경우는 0 또는 1 둘다 올수 있으므로 확정이 안됬음)
2) N 자리에 오는 수가 1일 때
... 0or1, 0, 1
이므로 N번째, N-1번째 경우는 확정이 되었다. 다른 값은 못온다.
따라서 이 경우에 경우의 수는 dp[N-2]라고 할 수 있다.

따라서 점화식은 dp[N] = dp[N-1] + dp[N-2]라고 할 수 있다.

또한, 이 문제에서 범위가 90까지 이므로 int의 범위를 벗어난다.
그에 따라 배열을 long타입으로 선언하였다.

다만 문제를 해결하면서 의아 했던점이,

else if(dp[N] != 0)
	return dp[N];

이 부분이 없으면 시간 초과 오류가 발생한다는 것이다.
추측건데, 저 코드가 이미 알고있는 dp[]값에 대해 미리 계산된 값을 사용하고, 점화식에 굳이 한번 더 시간을 쓰지 않게 해줘서 시간 단축을 시켜주는 것 같다.