C++ / 프로그래머스 / 아방가르드 타일링

문제

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

프로그래머스

문제풀이

n이 4부터는 새로운 방법의 타일링이 안 나오고 기존 모양에 붙여가는 줄 알았는데 아니었다.

n이 4일 때, 5일 때, 6일 때,... 계속 나온다.

 

새로운 방법의 타일링이 나오는 경우는 제외하고 덧붙이는 경우만 먼저 따진다.

 

기존타일링에 새로운 한 줄을 채울 때)

DP [idx-1]의 값과 같다

 

 

기존타일링에 새로운 두줄을 채울 때)

 

DP[idx-2]*2의 값과 같다.

 

기존타일링에 새로운 세줄을 채울 때)

 

X표는 위에 두경우에서 겹치는 경우이다.

이를 제외하면 5개이다.

따라서 DP[idx-3]*5의 값과 같다.

 

이런 식으로 n이 늘어날수록 DP[n] = DP[n-1] + DP[n-2] * 2 + DP[n-3] * 5는 고정이다.

하지만 n이 4일 때, 5일 때,... 계속 추가된다. 이제 이 규칙을 찾아야 한다.

 

n이 5일 때)

이 경우와 상하반전 또는 좌우반전을 한 경우 포함 2가지이다.

 

n이 6일 때)

여기에서 ㄱ자 블록만 위아래로 올리거나 내린 형태를 포함해 총 4가지이다.

 

n이 7일 때)

이 경우와 상하반전 또는 좌우반전을 한 경우 포함 2가지이다.

계속 n을 늘리면서 반복하면 패턴이 보인다.

 

for (idx2 = 4; idx2 <= idx; ++idx2) {
    if (idx2 % 3 == 0) {
        DP[idx] += (DP[idx - idx2] * 4 % DIV);
    }
    else {
        DP[idx] += (DP[idx - idx2] * 2 % DIV);
    }
}

for문으로 표현하면 이런 식이 나오는데 이 상태로 냈더니 시간초과가 났다.

답에 거의 근접한 것 같아서 식으로 나열하고 규칙을 더 찾아보기로 했다.

DP2[4] = DP[0]*2
DP2[5] = DP[0]*2 + DP[1]*2
DP2[6] = DP[0]*4 + DP[1]*2 + DP[2]*2
DP2[7] = DP[0]*2 + DP[1]*4 + DP[2]*2 + DP[3]*2
DP2[8] = DP[0]*2 + DP[1]*2 + DP[2]*4 + DP[3]*2 + DP[4]*2
DP2[9] = DP[0]*4 + DP[1]*2 + DP[2]*2 + DP[3]*4 + DP[4]*2 + DP[5]*2

DP2 [idx] = DP2[idx-1] + DP[idx-4]*2가 계속 꾸준히 겹친다.

그러다 idx가 6일 때만 특정 부분에서 *2를 더해줘야 한다.

그래서 for문을 추가해 해당 부분을 더해줬다.

전 식이랑 얼마나 차이 나는지는 잘 모르겠지만 통과했으니 됐다...

 

 

이 문제에서 제일 중요한 점은 ㄱ자 블록으로 인해 계속 새로운 블록이 나온다는 점과

1,000,000,007로 계속 나눈 나머지로 저장해야 된다는 점이다.

 

이 풀이 보다 다른 블로그나 코드를 보면 깔끔한 풀이가 있으니 참고만 바란다.

 

코드

#include <string>
#include <vector>
#define DIV 1000000007
using namespace std;

int solution(int n) {
    long long idx(0), idx2(0);
    vector<long long>DP(n + 1, 0);
    vector<long long>DP2(n + 1, 0);
    DP[0] = 1;
    DP[1] = 1;
    DP[2] = 3;
    for (idx = 3; idx <= n; ++idx) {
        DP[idx] = ((DP[idx - 1] + DP[idx - 2] * 2) % DIV + DP[idx - 3] * 5) % DIV;
        if (idx > 3) {
            DP2[idx] += ((DP2[idx - 1] + DP[idx - 4] * 2) % DIV);
            DP2[idx] %= DIV;
            for (idx2 = 2; idx2 <= (idx / 3); idx2++) {
                DP[idx] += (DP[idx - idx2 * 3] * 2 % DIV);
            }
            DP[idx] += DP2[idx];
            DP[idx] %= DIV;
        }
    }
    return DP[n];
}