프로그래머스 - 연습문제 - 3 x n 타일링

https://school.programmers.co.kr/learn/courses/30/lessons/12902

프로그래머스

---

문제 설명

가로 길이가 2이고 세로의 길이가 1인 직사각형 모양의 타일이 있습니다. 이 직사각형 타일을 이용하여 세로의 길이가 3이고 가로의 길이가 n인 바닥을 가득 채우려고 합니다. 타일을 채울 때는 다음과 같이 2가지 방법이 있습니다

• 타일을 가로로 배치 하는 경우
• 타일을 세로로 배치 하는 경우

예를들어서 n이 8인 직사각형은 다음과 같이 채울 수 있습니다.

직사각형의 가로의 길이 n이 매개변수로 주어질 때, 이 직사각형을 채우는 방법의 수를 return 하는 solution 함수를 완성해주세요.

---

제한사항

• 가로의 길이 n은 5,000이하의 자연수 입니다.
• 경우의 수가 많아 질 수 있으므로, 경우의 수를 1,000,000,007으로 나눈 나머지를 return해주세요.

---

입출력 예제

n	result
4	11

---

풀이

이전에 풀었던 2 * n 문제와 마찬가지로 dp 문제였다.

dp 문제의 경우 규칙을 찾아내는 것이 가장 중요한데 찾지 못해 결국은 구글링을 통해 규칙을 찾고 공부를 했다.

f(2)의 경우에는 3가지의 경우의 수가 존재하고

f(4)의 경우 f(2)의 타일을 놓는 법을 이어 붙이는 방법을 사용해 f(2) * 3에 f(2)에 존재하지 않던 방식 2가지 경우가 추가가 되어 f(4) = f(2) * 3 + 2 = 11의 결과를 얻을 수 있다.

여기서 그럼 f(n) = f(n - 2) * 3 + 2가 규칙인가 했는데 아니었다.

f(6)의 경우 f(4)에서 사용된 방법에 f(2)를 두는 방법 3가지를 곱하고 특수한 경우 2가지를 추가하는 것 까지는 동일하기에

f(6) = f(4) * 3 + 2까지는 동일하지만 이 방법은 n = 4인 부분에 n = 2인 부분을 뒤에 붙여서 얻은 방법이기에 n = 2인 부분이 앞에 n = 4인 부분이 뒤에 오는 경우가 추가가 되기에 f(2) * 2를 추가로 더해줘야 한다.

즉 f(6) = f(4) * 3 + 2 + f(2) * 2 = 11 * 3 + 2 + 3 * 2 = 35 + 6 = 41이다.

이후로는 f(8)의 경우 f(8) = f(6) * 3 + 2 + f(2) * 2 + f(4) * 2로 n = 4인 부분이 앞 다시 n = 4인 부분이 뒤에 오는 경우가 추가되듯이 f(n - 4) * 2가 누적되어 더해진다는 것을 알 수 있다.

---

코드

class Solution {
    public int solution(int n) {
        int answer = 0;
        int mod = 1000000007;
        
        long[] floor = new long[5001];
        
        // 타일은 n이 짝수일 때만 꽉 채워진다.
        floor[2] = 3;
        floor[4] = 11;
        
        // f(n - 4) * 2를 지속적으로 더해주는 temp
        long temp = 0L;
        for(int i = 6; i <= n; i += 2) {
            // f(n) = f(n - 2) * 3 + 2 + ((n - 4)시그마 k = 1 f(2k)) * 2
            floor[i] = floor[i - 2] * 3 + 2 + (temp += floor[i - 4] * 2);
            // 모듈러 함수 적용
            floor[i] %= mod;
        }
        
        answer = (int) floor[n];
        
        return answer;
    }
}