카테고리 없음

DP문제 백준 2193

벤치마킹 2018. 5. 8. 02:11


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

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


  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;

}