백준 2193 이친수

문제

문제링크 : https://www.acmicpc.net/problem/2193

풀이전략

1. 이친수는 반드시 1로 시작하고, 1이 두번 연속으로 나타나지 않아야 하는 제한조건을 가지고 있다.
2. 1로 시작하기 때문에 2번째 숫자는 반드시 0이다.
3. 5자리 숫자 10000 은 100 과 1000의 합으로 구성됨을 그림을 그리면서 파악한다.
4. 오버플로우가 날 수 있음을 항상 잊으면 안된다.
   pinaryNum(n+1) = pinaryNum(n) + pinaryNum(n-1)

코드

#include<bits/stdc++.h>

using namespace std;

#define mine

int N;
long long dp[91];
long long pinaryNumber(int n){
    if(n == 1) return 1;
    if(n == 2) return 1;
    long long& ret = dp[n];
    if(ret != -1) return ret;
    return ret = pinaryNumber(n-1) + pinaryNumber(n-2);
}

int main(){
    ios_base::sync_with_stdio(false);
    // freopen("../input.txt","rt",stdin);
    
    memset(dp, -1, sizeof(dp));
    cin >> N;
    
    cout << pinaryNumber(N) << endl;
    

    return 0;
}

소감

규칙만 찾는다면 문제는 쉽게 풀수 있다. 고등학생 때 점화식 풀던 기억이 나 흥미로웠다. 단 항상 오버플로우가 나올 수 있음을 체크하고, base case에 유의한다.