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

문제는 다음과 같습니다.

저는 거의 모든 dp문제를 초항 구하기 그리고 점화식 세우기 이 두가지를 구한 후에 풉니다.

1. n=1일때 a(1)=1
2. n=2일때 a(2)=2

그리고 n번째 규칙은 다음과 같습니다.

타일을 마지막으로 붙인 경우를 확인해보면,
마지막 타일을 2x1 타일을 붙인 경우 => a(n-1)+ <2x1 타일>
마자막 타일을 1x2 타일을 두 개 붙인 경우 => a(n-2) + <2x2 타일 2개>

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

a(n) = a(n-1) + 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)+func(num-2))%10007;
}


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

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

2/5 토요일 복습)

오 복습할때에는 bottom-up 방식으로 풀었는데, 이 전에서는 top-down을 이용했네요.

복습때 푼 풀이는 다음과 같습니다.

#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]=2;

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