2193 Dynamic -이친수 구하기

 

3 

우선 첫글자는 무조건 1이고

두번째는 2이상일때는 무조건 0

세번째부터가 문제 

3이 들어오면 100에서 시작해서 101 110 ㅇ이런식으로 갈때 조건을 검사해야하는듯..

//이런줄 알았음 조건을 다 계산해야 하는 줄 알았는데

역시 내가 점화식을 못세운탓..

 

되게 간단하게 풀 수 있는 문제였다..

우선 경우의 수를 예시로 쫌 보자

3자리의 경우

100 101

4자리의 경우

1000 1001 1010 

5자리의 경우

10000 10001 10010 10100 10101

 

이게 다이나믹인걸 아니까 그 전과 어떤 관계가 있는지 잘봐야함

다이나믹인지 모를때는 뭐..알아서 알아내야지 큼

전과의 관계를 보면

n자리의 경우 n-1자리에서 마지막이 0으로 끝나면 뒤에 0또는 1이 붙는게 가능하고

마지막이 1로 끝나면 0만 붙을 수 있다.

=>

n자리의 경우중 끝자리가 0인것의 개수=n-1자리에서 1로끝난거+0으로 끝난것의 개수

//                               1인것의 개수=n-1자리에서 0으로 끝난것의 개수

dp[n][0]=dp[n-1][0]+dp[n-1][1]

dp[n][1]=dp[n-1][0]

 

이걸 사용하면 아주 쉽게 풀 수 있다.

 

그리고 밑에는 자료형의 크기/범위인데 N의 범위가 90이다보니 int로는 커버가 안되는듯

 

c언어 자료형 크기/범위

//int로 하니까 정수 범위를 넘어서 long long사용함

C에서 long은 Int 랑 범위가 같으니까

Long long사용

#include<iostream>
#include<string.h>

using namespace std;

int main(void) {
	int num;
	long long **dp;
	long long result;
	cin >> num;
	dp = new long long*[num+1];
	for (int i = 0;i <(num+1);i++) {
		dp[i] = new long long[2];
		memset(dp[i], 0, sizeof(long long)*2);
	}
	dp[1][0] = 0;
	dp[1][1] = 1;

	for (int j = 2;j <=num;j++) {
		dp[j][0] = dp[j - 1][1] + dp[j-1][0];
		dp[j][1] = dp[j - 1][0];
	}

	result = dp[num][0] + dp[num][1];
	cout << result<<endl;
	return 0;

}