[BaekJoon/백준] 11726번 C++

규칙을 찾으면 되는 문제였고

동적계획법 문제였다.

 

즉, 점화식을 세워서 문제를 풀 수 있었다.

 

직접 n = 5일때까지 한번 구해봤다.

2 x 1 : 1개

2 x 2 : 2개

2 x 3 = 3개

2 x 4 = 5개

2 x 5 = 8개

 

해보니까 규칙이 보였다.

피보나치 형태로 증가하고 있었다. 이를 점화식을 세워 코딩했다.

#include <iostream>

int arr[1001] = {0, 1, 2, }; // 0번째 인덱스는 안쓸거고, 1번째 인덱스부터 1, 2...
int input;

using namespace std;

int main() {
    
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    
    cin >> input;
    
    for(int i = 3; i <= input; i++) {
        arr[i] = (arr[i - 2] + arr[i - 1]) % 10007;
    }
    
    cout << arr[input];
}