[Programmers] 프로그래머스 Lv.3 아방가르드 타일링 문제풀이(C++)

 

 

 

처음 아이디어, 이후 직접 그려보면서 규칙 찾아내기, 점화식 구한 후 MOD 연산 적용까지 모두가 한번에 안떠올랐던 문제..ㅠ

#include <string>
#include <vector>
#include<iostream>
#define MOD 1000000007
using namespace std;
/*
<문제>
가로 n, 세로 3인 판을 두가지 의 타일로 타일링하는 경우의 수 반환
각 타일은 90도씩 회전 가능, 개수제한없음
n<=10만
경우의수 1000000007로 나눈 나머지 리턴
 
<풀이>
A(X) = 시그마 i=1부터X-1까지 A(X-i)*S(i) + S(X) 임을 이용
 * A(X) = X*3에서 아방가르드 타일링 경우의 수, S(X) : X*3에서의 새로운 블록의 개수
직접 그려보면서 S(1)=1, S(2)=2, S(3)=5, S(4)=2, S(5)=2, S(6)=4 임을 알아내야함
이후 S(7)=2, S(8)=2, S(9)=4 ... 등 2, 2, 4가 반복됨 -> 이를 이용해서 A(X), A(X+3) 차이를 계산하면 
A(X) = A(X-1)+2A(X-2)+6A(X-3)+A(X-4)-A(X-6) 식 얻을 수 있음
-> 이걸로 계산하되, 수가 매우 크므로 MOD연산 잘 적용시켜서 구하면 답 나옴
*/
 
int solution(int n) {
    if (n == 1) return 1;
    if (n == 2) return 3;
    if (n == 3) return 10;
    unsigned long long A[100001];
 
    A[0] = 1; A[1] = 1; A[2] = 3; A[3] = 10; A[4] = 23, A[5] = 62; A[6] = 170;
 
    for (int i = 7; i <= n; i++) {
        unsigned long long tmp = 
            ((((A[i - 1]%MOD + (2 * A[i - 2])%MOD) % MOD) + (((6 * A[i - 3]%MOD) + A[i - 4]%MOD)%MOD))%MOD  - (A[i - 6]%MOD) + MOD)%MOD;
        A[i] = tmp;
    }
 
    return A[n] % MOD;
}