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

11726번: 2×n 타일링 (acmicpc.net)

11726번: 2×n 타일링

---

규칙성을 알아보기 위해 일일이 구해보면..

 

n=1 일 때, 1가지

n=2 일 때, 2가지

n=3 일 때, 1+2 = 3가지 (모두 세로로 서 있는 거 1가지 + 한개만 세로로 있고 2개가 누워있는 거 2가지)

n=4 일 때, 2+3 = 5가지 (모두 세로로 서 있는 거 1가지 + 모두 누워있는 거 1가지, 2쌍만 누워있는거 3가지)

n=5 일 때, 8가지

n=6일때, 13가지

n=7일때, 21가지

n=8일때 34가지

n=9일때, 55가지 (예제 출력 2번 확인)

 

점화식을 지어보면

T(n) = T(n-1) + T(n-2)

 

그렇게 해서 DP로 코드를 짰는 데 틀렸다

문제의 코드는

#include <iostream>
using namespace std;

int main()
{
    int n;
    cin >> n;
    
    int T[n] = {1, 2, };
    
    for(int i=2; i<n; i++){
        T[i] = T[i-1] + T[i-2];
    }
    
    cout << T[n-1] % 10007;
    return 0;
}

???

그래서 구글링을 해봤는데 분명히 맞는대 계속 틀리단다

[백준] 11726 2xn 타일링 C++ (DP) (velog.io)

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

결국 뭐가 틀렸는 지 찾지 못했다,, 

알려주세요

결국 코드는 위 링크랑 똑같이 했다

#include<iostream>
using namespace std;

int main()
{
    int dp[100001];
    int n;
    scanf("%d",&n);

    dp[1] = 1;
    dp[2] = 2;

    for(int i=3; i<=n; i++)
    {
        dp[i] = (dp[i-1] + dp[i-2]) % 10007;

    }
    printf("%d\n", dp[n]);
    return 0;
}