[백준] 2193번: 이친수(DP)

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

2193번: 이친수

코드

import java.util.Scanner;

public class Main {

	public static void main(String[] args) {
		Scanner scan = new Scanner(System.in);
		int N = scan.nextInt();
		long[] dp = new long[91];
		dp[1] = 1;
		dp[2] = 1;
		for(int i=3; i<=90; i++) {
			dp[i] = dp[i-1] + dp[i-2];
		}
		
		System.out.println(dp[N]);
		scan.close();
	}

}

풀이

대표적 DP 문제입니다.

dp[N] -> N개 자리수에 이친수를 만족하는 경우의 수 라고 생각해 봤을때, 

N자리에 올 수 있는 숫자는 0 과 1 이다.

 

N = 6일때,

1) xxxxx0

2) xxxxx1

위 두가지의 케이스가 있다.

첫번째 케이스는, 마지막에 0이 오는 경우로, 그 앞에는 0과 1이 올 수 있다.

따라서 dp[N] = dp[N-1]과 동일하다.

두번째 케이스는, 마지막에 1이 오는 경우로, 그 앞에는 무조건 0이 와야한다.

그럼 그 앞앞은? 0과 1이 올 수 있다. -> xxx001 혹은 xxx101

따라서 dp[N] = dp[N-2]와 동일하다.

 

위의 결론을 바탕으로 점화식을 세우면,

dp[N] = dp[N-1] + dp[N-2] 라는 식이 성립한다.

 

설명이 잘 되어있는 글을 참고해서 작성해보면,

이친수의 조건에 의해 이친수는 무조건 1 0 으로 시작해야한다.

https://blog.naver.com/occidere/220788046159

N=4일때, 1 0 을 제외한 네모(2자리)에 들어올 수 있는 숫자는 00, 01, 10 이다.

00, 01, 10 숫자는 N=2일때, N=3일때 이미 사용했던 숫자들이다.

https://blog.naver.com/occidere/220788046159

따라서 dp[N] = dp[N-1] + dp[N-2] 라는 점화식이 성립한다.

 

* 문제에서 조심해야 할 점은, N의 범위(자릿수)는 90까지인데, 일정 항을 넘어가면 int의 범위를 벗어나버린다.

따라서 배열의 자료형은 int가 아닌 long으로 선언해야 정답으로 제출된다.