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

문제

문제 설명

 

 

풀이

 

[문제 풀이]

 

이 문제는 경우만 잘 파악하면 쉽게 풀 수 있는 문제다.

 

가로 세로가 2*3 인 사각형에 2*3인 사각형을 더하면 4*3인 사각형을 만들 수 있다.

 

이를 이용하면 길이가 n인 사각형을 만들기 위해서는

[0*3인 사각형, n*3인 사각형] + [1*n인 사각형, (n-1)*3인 사각형] ... 을 전부 계산하면 된다.

 

+ 참고로 이 문제에서 길이가 홀수인 사각형은 만들 수 없다.

 

 

이를 이용하면 문제를 풀 수 있는데 그 전에 알고 넘어가야 되는 게 있다.

위 그림과 같이 길이가 6인 사각형은

[2*3인 사각형, 4*3인 사각형] 처럼 볼 수 있고, [4*3인 사각형, 2*3인 사각형] 으로도 볼 수 있다.

 

이 경우 중복이 되기 때문에 중복을 방지해야 한다.

 

중복을 방지하기 위해서는 고유한 사각형이 몇개인지 구하면 된다.

 

먼저 길이가 2인 사각형이 몇 개인지 생각해보자

 

아래 그림과 같이 3개 존재한다는 사실을 알 수 있다.

 

 

그렇다면 길이가 4인 사각형은 몇 개 일까?

총 11개지만 아래 그림처럼 [2*3인 사각형, 2*3인 사각형]으로 만들어진 경우는 순수한 길이가 4인 사각형에서 제외해 주어야 한다.

(중복 제거를 위해)

 

그러면 위 그림과 같이 [2*3인 사각형, 2*3인 사각형]이 3*3 = 9 개 있고

 

아래 그림처럼 순수하게 길이가 4인 사각형은 2개 존재한다는 사실을 알 수 있다.

 

위 그림에서 알 수 있듯이 n의 길이가 6, 8, 10인 사각형도 마찬가지로 길이가 순수하게 n인 사각형은 2개만 존재한다.

 

 

그러므로 이를 이용해 길이가 n인 사각형을 점화식으로 나타내면

 

DP[n] = DP[n-2] + DP[n-2]*2 + DP[n-4]*2 + DP[n-6]*2 + ... + DP[2]*2 + 2(순수하게 길이가 n인 사각형 2개)

가 된다.

 

맨 앞에 DP[n-2]를 한번 더 더해주는 이유는 길이가 2일 때만 왼쪽과 같은 고유한 사각형이 존재하기 때문이다.

 

(오른쪽은 길이가 4인 고유한 사각형이 아니라 길이가 2인 고유한 사각형이 2개 붙어있는 경우다)

 

 

이를 이용해 길이가 n인 사각형의 개수를 구하면 된다.

 

 

 

​

[아이디어 정리]

1. 길이가 n인 사각형에서 n이 홀수인 경우는 0이다.
2. [길이가 n인 사각형] = [길이가 n-2인 사각형] + [길이가 n-2인 사각형]*2+[길이가 n-4인 사각형]*2 ... + 2 인 점화식으로 구할 수 있다.
3. 길이가 n인 사각형의 개수를 1000000007로 나눠 return한다.

 

 

Code

 

 

#include <string>
#include <vector>

using namespace std;

const long long mod=1000000007;
int solution(int n) {
    int answer = 0;
    vector<long long> ans(5001,0);
    ans[2]=3;
    for (int i=4; i<=n; i+=2)
    {
        ans[i]+=2;
        ans[i]+=ans[i-2];
        for (int j=i-2; j>=0; j-=2)
        {
            ans[i]+=ans[j]*2;
            ans[i]%=mod;
        }           
    }
    return ans[n];
}

 

 

Code2

 

 

#include <string>
#include <vector>

using namespace std;

const long long mod=1000000007;
int solution(int n) {
    int answer = 0;
    vector<long long> ans(5001,0);
    ans[2]=3;
    long long t=ans[2];
    for (int i=4; i<=n; i+=2)
    {
        ans[i]+=2;
        ans[i]+=ans[i-2];
        ans[i]+=t*2;
        ans[i]%=mod;
        t+=ans[i];
        t%=mod;       
    }
    return ans[n];
}

 

 

---

 

타일링 문제는 몇번 풀어보면 그 뒤로 요령이 생겨 잘 풀리는 문제인 것 같다.

프로그래머스