[BOJ] C++ 2193: 이친수 - DP 테이블링 연습하기

2193번: 이친수

---

DP문제인데, DP문제의 가장 중요한 점은 문제를 보고 DP를 떠올릴 수 있어야 하고 테이블링을 할 수 있어야 한다.

 

가장 먼저 떠오른 풀이는 백트래킹이다. n자리를 모두 체크해보고 이친 수인지 판단하는 방법인데, 2^n의 데이터를 검사해야 하므로 바로 패스했다.

 

또 바로 떠오르는 풀이가 없으니 일단 n=1부터 n을 증가시키면서 규칙을 찾아보았다. 다행히 n=3부터 n=1에서 구했던 부분을 써먹을 수 있었다. n을 계속 늘려가면서 6 정도까지 관찰해 보니 DP를 이용하면 될 것 같았다. 테이블링도 바로 했다.

 이처럼 n=k-2 ... n=1까지 모두 더하고 1을 더해주면 되는데, 계산하다 보니 피보나치와 똑같은 형태를 가져서 피보나치로 바로 구현했다. n이 90까지 가므로 long long을 사용했다.

/** DP 2193 이친수 **/
#include <iostream>
#include <vector>
#include <algorithm>
#include <string>
using namespace std;

long long dp[100];

int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);

    long long n;
    cin >> n;

    fill(dp, dp + n + 1, 0);
    dp[1] = dp[2] = 1;

    // dp[k] = dp[k-2] + dp[k-3] + ... + dp[1]
    // => 피보나치
    for (long long i = 3; i <= n; i++)
        dp[i] = dp[i - 1] + dp[i - 2];

    cout << dp[n];
}