05.02. 이친수 [Dynamic Programming][백준 2193]

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

2193번: 이친수

 

Algorithm classification : Dynamic Programming

 

05.02.1. Problem

A number made up of only 0 and 1 is called a binary number. Some of these binary numbers have special properties, and they are called binary numbers. A binary number satisfies the following properties.

• Binary numbers do not start with 0.
• In binary numbers, 1 does not appear twice in a row. That is, it does not have 11 as a substring.

For example, 1, 10, 100, 101, 1000, 1001, etc. become binary numbers. However, 0010101 and 101101 are not binary numbers because they violate rules 1 and 2, respectively.

Write a program to find the number of N-digit binary numbers given N(1 ≤ N ≤ 90).

 

05.02.2. Input limit

N is given in the first line.

 

05.02.3. Output

Prints the number of N-digit binary numbers in the first line.

 

05.02.4. Solution

DP table과 점화식을 정의하는 것이 가장 중요합니다. dp[N][M] = 길이가 N이고 첫 자리가 M인 이친수의 수라고 하면 dp[N][1] = dp[N-1][0], dp[N][0] = dp[N-1][0] + dp[N-1][1]이 됩니다. 남은 것은 초기화와 출력입니다.

long long dp[100][2] = {0};

void cal(int n){
	if(dp[n][1] != 0) return;
	cal(n-1);
	dp[n][0] = dp[n-1][0] + dp[n-1][1]; 
	dp[n][1] = dp[n-1][0];
}

int main()
{
	int n;
	scanf("%d", &n);
	
	dp[1][0] = 0;
	dp[1][1] = 1;
	dp[2][0] = 1;
	dp[2][1] = 0;
	
	cal(n);
	
	printf("%lld", dp[n][0] + dp[n][1]);
	
	return 0;
}

 

	for(i = 3; i <= n; i++){
		data[i][0] = data[i-1][0] + data[i-1][1];
		data[i][1] = data[i-1][0];
	}
	
	printf("%lld\n", data[n][0] + data[n][1]);