[프로그래머스] 3 x n 타일링

문제 주소 : programmers.co.kr/learn/courses/30/lessons/12902

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

문제 확인

 

dp 문제로 수열식으로 풀 수 있습니다.

홀수인 경우 모든 답이 0이며 짝수인 경우 생길 수 있는 경우의 수를 체크하면 쉽게 풀 수 있습니다.

 

풀이

 

n을 2 단위로 생각하면 두 가지 종류로 나눌 수 있습니다.

1. 영역이 겹치는 문양 : 매 단계에서 새로 생기는 문양
2. 영역이 분리된 문양

겹치는 문양의 경우 매 단계에서 2개 추가됨

n = 2

n = 6(뒤집어서 2개)

분리된 문양의 경우

따라서 n이 2 증가할 때 생각할 수 있는 경우의 수는 다음과 같습니다.

이를 수식으로 나타내면 f(n) = f(n-2) * 3 + f(n-4) * 2 + f(n-6) * 2 + .... + f(2) * 2 + 2가 됩니다.

f(n-4)부터 추가문양 만을 더하는 이유는 앞서 계산한 값들이 중복되기 때문입니다.

 

코드

#include <string>
#include <vector>
 
using namespace std;
 
int solution(int n) {
    if (n % 2) return 0;
    else {
        unsigned long long sum = 3, prev = 3, cur = 3;
        for (int i = 2; i < n; i += 2) {
            cur = prev + sum * 2 + 2;
            cur %= 1000000007;
            prev = cur;
            sum += cur;
        }
        return (int)(cur % 1000000007);
    }
 
}