[프로그래머스 LV4] 3 x n 타일링 (DP) [C++]

 

programmers.co.kr/learn/courses/30/lessons/12902#qna

코딩테스트 연습 - 3 x n 타일링

 

백준의 이 문제와 똑같다. 밑의 설명을 참고하면 좋을 것 같다.

bbeomgeun.tistory.com/30

[baekjoon 2133] 타일 채우기- DP(동적 프로그래밍) (C++)

차이점은 백준 문제는 30까지 구하지만 프로그래머스는 n이 5000까지 존재한다.

따라서 배열에 % 1,000,000,007의 값으로 나눈 나머지 값을 저장해야 한다.

 

#include <string>
#include <vector>
#define MOD 1000000007

using namespace std;

long long arr[5001];


int solution(int n) {
    int answer = 0;
    if(n % 2 != 0)
        return 0;
    arr[0] = 1;
    arr[2] = 3;
    
    for(int i = 4 ; i <= n ; i+=2){
        arr[i] = (arr[i-2] * 3);
        for(int j = 0 ; j <= i-4 ; j += 2){
            arr[i] += (arr[j] * 2) % MOD;
        }
        arr[i] %= MOD;
    }
    
    
    
    answer = arr[n] % MOD;
    
    return answer;
}

Long long 형으로 바꿔주고 나머지 값을 저장해준다.