[백준] 2193번 이친수 / C++

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

C++

#include<iostream>
using namespace std;

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    int N; long long arr1[100];
    cin >> N;
    arr1[0] = 0;
    arr1[1] = 1;
    arr1[2] = 1;
    for(int i = 3; i <= N; i++) {
        arr1[i] = arr1[i-1] + arr1[i-2];
    }
    cout << arr1[N];
}

문제풀이

• 문제를 보면서 N의 값에 따른 이친수의 개수가 규칙적으로 증가할 것이라고 생각했다. 따라서 N의 값에 따른 이친수의 개수를 직접 구했다. 구해보면서 f(x) = f(x-1) + f(x-2)라는 점화식을 찾을 수 있었다.

Comment

• 이러한 Dp유형의 문제는 직접 적고 구해보면서, 점화식을 찾는 것이 중요할 것 같다.