[2193] 이친수

풀이 1

dp[i][j]는 길이가 i이고 마지막 숫자가 j인 이친수의 수 이다. 현재 길이의 이친수가 되기 위해서는 이전 길이의 숫자 중 0과 1로 끝나는 것에 0을 붙히거나, 1로 끝나는 것에 0을 붙혀야 한다.

코드 1

#include

long long dp[2][91]; int n;

int main(void) { scanf(“%d”, &n); dp[0][1] = 0; dp[1][1] = 1; for (int j = 2; j <= n; j++) { dp[0][j] = dp[0][j - 1] + dp[1][j - 1]; dp[1][j] = dp[0][j - 1]; } printf(“%lld\n”, dp[0][n] + dp[1][n]); return 0; }

풀이 2

dp[i]는 길이가 i인 이친수의 수이다.
길이가 i-1인 이친수에서 0을 붙히거나, 길이가 i-2인 이친수에서 01을 붙혀서 만들 수 있다.

코드 2

#include <iostream>

long long dp[91];
int n;

int main(void) {
	scanf("%d", &n);
	dp[1] = 1;
	dp[2] = 1;
	for (int i = 3; i <= n; i++) {
		dp[i] = dp[i - 1] + dp[i - 2];
	}
	printf("%lld\n", dp[n]);
	return 0;
}