DP문제 백준 2193

이미 문제에서 점화식 ..을 유도하는 방법이 있는데  직접 써보면 이해가 좀 더 빠르다 

아래 조건을 만족하는 값의 예는 아래와 같다 

1. 이친수는 0으로 시작하지 않는다.
2. 이친수에서는 1이 두 번 연속으로 나타나지 않는다. 즉, 11을 부분 문자열로 갖지 않는다

N 1 -> 1

N 2 -> 10,

N 3- > 100, 101,

N 4- > 1000, 1001, 1010

이전 n-1 , n-2 에가 각각의 값을 구해볼수 있다 

N 5 -> 10000, 10001, 10100, 10010, 10101

결국 점화식은 dp[n] = dp[n-1] + dp[n-2]

code 상으로는 아래 값이다. 

#include <stdio.h> #include <iostream>  #include <vector> #include <string> #include <queue> #include <functional> #include <algorithm> #include <iostream> #include <vector> #include <cstring> using namespace std; #define MIN(a,b) (((a)<(b))?(a):(b)) #define MAX(a,b) (((a)>(b))?(a):(b)) #define ABS(a)  a<0 ?-(a):a // 절대 값 long long arr[1000000]; // dp  int N; int main(void) { int TC = 1, i; arr[0] = 0; arr[1] = 1; arr[2] = 1; arr[3] = 2;   cin >> N; for (i = 4; i <= 90; i++) arr[i] = arr[i - 1] + arr[i - 2]; cout << arr[N] << endl; return 0; }