[백준][2193]이친수

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

2193번: 이친수

풀이과정

 

1. dp 문제이다.

 

2. 이진수에서 0으로 시작하지 않으며, 1이 연속 되지 않는 값을 이친수라한다.

 

N자리 수가 0 일 경우엔 N - 1에 0과 1 모두 올 수 있으므로

dp[N][0] = dp[N-1][0] + dp[N-1][1] 을 구 할 수 있다.

 

N자리 수가 1일 경우엔 N - 1 자리엔 0 밖에 오지 못한다. 

dp[N][1] = dp[N-2][0] + dp[N-2][1] 의 식을 구 할 수 있다.

 

 

 

소스코드

#include<stdio.h>
typedef unsigned long long ull;
ull dp[91][2];

ull solution(int n) //재귀
{
	if (dp[n][0] > 0 || dp[n][1] > 0) {
		return dp[n][0] + dp[n][1];
	}

	dp[n][0] = solution(n - 1);
	dp[n][1] = solution(n - 2);

	return dp[n][0] + dp[n][1];
}

ull solution2(int n) //for
{
	for (int i = 3; i <= n; i++) {
		for (int j = 0; j < 2; j++) {
			dp[i][j] = (j == 0) ? dp[i - 1][0] + dp[i - 1][1] : dp[i - 2][0] + dp[i - 2][1];
		}
	}
	return dp[n][0] + dp[n][1];
}

int main()
{
	int n;
	dp[1][0] = 0;
	dp[1][1] = 1;
	dp[2][0] = 1;
	dp[2][1] = 0;
	scanf("%d", &n);
	printf("%llu\n", solution2(n));
}