[백준/C++] 11727번_2xn 타일링2

문제는 다음과 같습니다.

초항을 구하면 다음과 같습니다.
n=1, a[1]=1
n=2, a[2]=3

점화식의 규칙은 다음과 같습니다.

1. 마지막 타일을 1x2 한 개를 붙인 경우 => a(n-1) + <1x2 타일 1개>
2. 마지막 타일을 2x1 두 개를 붙인 경우 => a(n-2) + <2x1 타일 2개>
3. 마지막 타일을 2x2 한 개를 붙인 경우 => a(n-2) + <2x2 타일 1개>

즉, 점화식은 다음과 같습니다.

a(n) = a(n-1) + 2*a(n-2) (단, n>=3)

전체 코드는 다음과 같습니다.

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

int a[1001]={0, };

int func(int num){
  if(a[num]) return a[num];

  return a[num]=(func(num-1)+2*func(num-2))%10007;
}


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

    a[1]=1;
    a[2]=3;
    int n;
    cin>>n;
    
    cout<<func(n)<<endl;
    return 0;
}

2/5 토 복습)

이번에 복습하면서 푼 풀이는 다음과 같습니다.
복습에서는 bottom-up 방식을 이용하여 풀었습니다.

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

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

    int dp[1001]={0, }; int n; cin>>n;
    dp[1]=1; dp[2]=3;

    for(int i=3; i<=n; i++){
      dp[i]=(dp[i-1]+(2*dp[i-2]))%10007;
    }
    cout<<dp[n]<<endl;
    return 0;
}