[백준][C++] 11726 2xn 타일링

11726 2xn 타일링

11726번: 2×n 타일링

문제 풀이

GitHub - minyoung529/AlgorithmStudy: 여러 알고리즘 문제를 푸는 저장소입니다.

 

앞의 n이 1, 2, 3, 4, 5일 때의 테스트케이스를 구하고 점화식을 세운 문제!

신기하게도 피보나치 수열이 나왔다!!!

 

그림으로 그려본 테스트 케이스.

1 2 3 5 8...

어디서 본 식이다!

난 저 식을 보고 헉했다...

 

구현해 본 코드

#include<bits/stdc++.h>
using namespace std;

int main()
{
    int n;
    unsigned long long int dp[1001] = { 0,1,2,3,0 };

    for (int i = 4; i <= 1000; i++)
    {
        dp[i] += (dp[i - 1] + dp[i - 2]) % 10007;
    }

    cin >> n;
    cout << dp[n];
}

 

하지만... 사실 조금의 집녑과 운으로 맞춘 문제라... 어떻게 피보나치 식이 나오는지 몰랐다.

고민 고민해도 계속 모르겠어서 질문 검색 탭에서 한 게시물의 댓글을 봤다.

진짜 천재 같은 사람... 진짜 진짜 천재 같은 발상!!

 

나도 저렇게 논리적으로 점화식을 짤 수 있도록... 다양한 DP 문제를 풀면서 실력을 키워야겠다... 기다려라 DP...