https://programmers.co.kr

문제:

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

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

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

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

풀이:

가로의 길이가 홀수라면 타일을 놓을 수 없으므로 제외한다.

짝 수일때, 가로의 길이가 n이라면

a[n / 2] = 3 * a[(n / 2) - 1] + 2 * (a[(n / 2) - 2] 까지의 합) 으로 나타낼 수 있다.

이 때, 경우의 수가 매우 크므로 1,000,000,007로 나눈 나머지를 출력하도록 한다.

또한, 자료형을 long long으로 바꾸도록 하자.

a[n / 2] = 4 * a[(n / 2) - 1] - a[(n / 2) - 2] 로도 풀 수 있으나, 수가 매우 커지면서 4 * a[(n / 2) - 1] < a[(n / 2) - 2] 이 되는 경우의 수가 생기게 되어 마이너스 값이 나올 수 있으므로 이렇게 풀지 말자.

코드:

사용언어 : c++

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16

#include <string>
#include <vector>

using namespace std;

int solution(int n) {
    vector<long long> a = {1, 3};
    long long sum = 0;
    if(n % 2)
        return 0;
    for(int i = 2; i <= n / 2; i++){
        sum += a[i - 2] % 1000000007;
        a.push_back((3 * a[i - 1] + 2 * sum) % 1000000007);
    }
    return a[n / 2];
}