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

미숙한 블로그 주인이 코딩테스트 문제를 풀어가는 과정을 담은 글입니다. 이 풀이가 효율적인 풀이가 아닐 수 있으며, 부정확한 정보가 많이 있을 수 있습니다. 보완해야할 점이 있다면 댓글로 남겨주세요!

 

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

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

3 x n 타일링

문제

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

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

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

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

 

제한사항

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

 

풀이

입출력 예시

 

풀이

먼저 n이 홀수라면 항상 경우의 수가 0임을 알아내었다. 그러니, n이 짝수일 때만 고려하면 되었다. n 이 6일 때의 경우를 제공해주었다면 규칙 찾기가 조금이라도 더 수월했겠지만(그래도 오래걸렸겠지만) 일단은 찾았으니...

 

n 이 짝수가 된다면 아래와 같이 흘러간다.
n = 2 일 때 3가지,
n = 4 일 때 11가지,
n = 6 일 때 41가지,
n = 8 일 때 153가지,

 

위 과정을 통해 찾을 수 있는 규칙은, (n 일 때의 경우의 수) = (n - 2 일 때 경우의 수) x 4 - (n - 4 일 때 경우의 수) 라는 것이다.

점화식으로 나타내면 아래와 같겠다.

f(n) = f(n - 2) x 4 - f(n - 4)

 

문제에서는 경우의 수가 매우 커질 수 있으니 1,000,000,007로 나눈 나머지를 반환하라고 되어있다. 그래서 그렇게 해주었다.

long long n_1 = 1;
long long tmp;
        
for (int i = 2; i <= n; i += 2) {
    tmp = answer;
    answer = ((answer * 4) - n_1) % 1000000007;
    n_1 = tmp;
}

그리고 바로 실패가 떠버렸다.

 

왜 인지 분석해봤더니, 음수가 발생했던 것이었다. 뒤의 빼는 부분이 더 커지는 구간이 생겨서 그랬다. 그래서, 분배 법칙을 이용해 식을 조금 바꿔주었다.

answer = ((answer * 4) % 1000000007 - n_1 % 1000000007 + 1000000007) % 1000000007;

 

이렇게 식을 바꿔주니 비로소 모든 테스트가 통과되었다.

 

#include <string>
#include <vector>

using namespace std;

int solution(int n) {
    long long answer = 1;
    
    if (n % 2 == 1) {
        return 0;
    }
    else {
        long long n_1 = 1;
        long long tmp;
        
        for (int i = 2; i <= n; i += 2) {
            tmp = answer;
            answer = ((answer * 4) % 1000000007 - n_1 % 1000000007 + 1000000007) % 1000000007;
            n_1 = tmp;
        }
    }
    
    return answer;
}