[ 백준 ] 14852번 - 타일 채우기 3 (C++)

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

14852번: 타일 채우기 3

 

 

[ 문제풀이 ]

 

1. 다음과 같은 점화식을 사용하여 문제를 풀어줍니다.

dp[ 1 ][ i ] = dp[ 1 ][ i - 1 ] + dp[ 0 ][ i - 3 ] 
dp[ 0 ][ i ] = 3 * dp[ 0 ][ i - 2 ] + 2 * dp[ 0 ][ i - 1 ] + 2 * dp[ 1 ][ i ] 

 

2. 수가 int 범위를 넘어갈 수 있으므로 long long 자료형을 쓰고, 1000000007을 Modulo를 통해 답을 출력합니다.

 

[ 소스코드 ]

#include<iostream>
#define ll long long
#define M 1000000007
 
using namespace std;
 
int N;
ll dp[2][1000001];
 
int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
 
    cin >> N;
 
    dp[0][0] = 1;
    dp[0][1] = 2;
    dp[0][2] = 7;
 
    for (int i = 3; i <= N; i++) {
        dp[1][i] = (dp[1][i - 1] % M + dp[0][i - 3] % M) % M;
        dp[0][i] = (3 * dp[0][i - 2] % M + 2 * dp[0][i - 1] % M + 2 * dp[1][i] % M) % M;
    }
 
    cout << dp[0][N];
}