수학적 규칙 찾기로 접근하면 더 쉬운문제…ㅎ

문제

  • 이친수란 이진수중 특별한 성질을 갖는 수로써 0으로 시작하지 않고 1이 중복해서 나오지 않는다. 예를들어 101은 이친수이지만 1011은 이친수가 아니다.
  • 숫자의 자리수 n이 주어졌을 때 n자리 이친수의 갯수를 출력하면 된다.

입력

  • 첫째 줄에 정수 n(1 ≤ n ≤ 90)이 주어진다.

출력

예제 입력
5
예제 출력
5

접근

  • 다이나믹 프로그래밍을 어떻게 사용할까?

내가 생각한 풀이

  • 사실 처음에는 규칙을 찾아서 금방 해결했다.
  • 하지만 다이나믹 프로그래밍이니 접근법을 다시 생각해본 결과 대부분의 다이나믹 프로그래밍과 마찬가지로 이전에 사용됐던 숫자들이 재사용 될 수 있다는 것을 알아냈다.
    • 예를 들어 4자리 수를 생각해보면 맨 앞이 0으로 시작할 수 없으니 1xxx라고 생각하고 xxx에 들어갈 수를 찾아보면 10의 자리 앞에 0을 붙인 010, 그리고 3자리수 100, 101이 들어갈 수 있다.
    • 5자리수 역시 1xxxx라고 가정해보면 xxxx자리에는 0100, 0101, 1000, 1010, 1001, 1010이 들어갈 수 있다.
  • 이러한 규칙을 통해 dp[i] = dp[i-1] + dp[i-2]라는 점화식을 세울 수 있다.

코드

#include<iostream>
using namespace std;

int main(void){
  int c;
  long long a[92];
  cin>>c;
  a[1] = 1;
  a[2] = 1;
  for(int i = 3 ; i<=c ;i++){
      a[i] = a[i-2] + a[i-1];
  }
  cout<<a[c];
  return 0;
}