DP > 2xn 타일링(11726번)

하씨 이것도 했던건데...

대체 강의를 어케 들었던게냐... 코테를 너무 쉬었던건가,,,

암튼 다시해봄!!

이것도 쉬워서 탑다운, 바텀업 둘다 했어!

 

---

풀이

여기서도 앞에서 풀었던 문제랑 똑같아!

D[n]이 2*n 사각형을 만드는 방법의 수를 의미해!

그럼 뭐겠어!

d[0]=0, d[1]=1, d[2]=2겠지?

이거 먼저 초기화하고 top down은 재귀로, bottom up은 n=3일떄부터 반복문으로 구현하면 되는거야!

 

 

---

Top-down

#include <iostream>
#define MAX 1001
using namespace std;

int d[MAX];

int go(int n){
    if(d[n]!=0) return d[n];
    d[n]=(go(n-1)+go(n-2))%10007;
    return d[n];
}

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    
    int n;
    cin>>n;
    d[0]=0;
    d[1]=1;
    d[2]=2;
    printf("%d\n", go(n));

    return 0;
}

 

bottom-up

#include <iostream>
#define MAX 1001

using namespace std;

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    
    
    int n;
    int d[MAX]={0, };
    cin >> n;
    d[0]=0;
    d[1]=1;
    d[2]=2;
    
    for(int i=3; i<=n; i++)
    {
        d[i] = (d[i-1] + d[i-2])%10007;
    }
    
    printf("%d\n",d[n]%10007);

    return 0;
}

 

맞다 그리고 잊고 있었는데

 

ios_base::sync_with_stdio(false);
cin.tie(nullptr);

이거 추가해두면 c++ 성능 좋아진다고 했어!

앞으로 코테 연습할때 헤더 추가하듯 추가하자!