백준 14852번 - 타일 채우기(3)

https://www.acmicpc.net/problem/14852

14852번: 타일 채우기 3

DP문제의 기본형에서 1*1의 타일이 생기면서 조금 더 생각을 할 필요가 있는 문제였다.

원래는 간단하게 DP[i]=DP[i-1]+DP[i-2] 의 형식으로 해결이 가능하지만,

 

1*1의 경우가 생김으로써 DP[i]=DP[i-1]*2 + DP[i-2]*3 의 경우를 생각해야 한다.

ㅁㅁㅁㅇ    ㅁㅁㅁ|    ㅁㅁ--    ㅁㅁ--       ㅁㅁㅇㅇ   

ㅁㅁㅁㅇ    ㅁㅁㅁ|    ㅁㅁ--    ㅁㅁㅇㅇ    ㅁㅁ--

 

여기에 밑에 경우를 생각해 줘야 한다. 즉, DP[i-3]*2의 경우, DP[i-4]*2의 경우, ... , D[0]*2의 경우를 생각해줘야한다.

ㅁㅁ--ㅇ    ㅁㅁㅇ--    

ㅁㅁㅇ--    ㅁㅁ--ㅇ

 

그래서 DP[i-3]+DP[i-4]+..DP[0]의 값을 저장한 DP[i][1]과
실제 갯수를 구하는 DP[i][0]을 구분해서 구현해주면 된다.

 

#include <iostream>
#define MOD 1000000007
using namespace std;

long long arr[1000000][2];

int main(){
    int n;
    cin>>n;
    arr[0][0]=0;
    arr[1][0]=2;
    arr[2][0]=7;
    arr[2][1]=1;
    for(int i=3; i<=n; i++){
        arr[i][1]=(arr[i-3][0]+arr[i-1][1])%MOD;
        arr[i][0]=(arr[i][1]*2+arr[i-1][0]*2+arr[i-2][0]*3)%MOD;
    }
    cout<<arr[n][0];
}