DP > 2xn 타일링 2 (11727번)

문제

---

풀이

퇴사하고 간만에 하는 알고리즘이란,,,

매일매일 아침에 7-9시나 10시까지 코테문제 3-5개씩 풀어야지! 했는데 오늘 11시에 일어났어

어제 고냥 그대로 잠들고 난리남...ㅋㅋ

그래...어제는 퇴사 첫날이자 개강 첫날이니까...

오늘은 근로 첫날인데 진짜 개꿀이네 이거

멀지만 않으면 20시간 걍 다 채우고싶다ㅠㅠ

수요일도 나오고 싶은거 꾹참았다..

암튼 풀이 대충 쓰면 

 

어제 밤에 그려놓고 오늘 푸는 알고리즘~..ㅎㅎ

이거 그 2*n타일링이랑 방식은 똑같은데 그냥 타일 하나 추가된거라 쉽게 품

그래서 코드도 거의 비슷해

top-down, bottom-up 2개 나눠서 풀었음

---

코드

 

Bottom-up

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

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

    return 0;
}

 

Top-down

#include <iostream>
#include <stdio.h>
#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) + 2*go(n-2))%10007;
    return d[n];
}

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

    return 0;
}