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

 

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

 

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

프로그래머스

---

 

 

해결전략

 

동적계획법 Dynamic Programming, DP

 

 

dp[i] = dp[i-2] * 3 + dp[i-4] * 2 + dp[i-6] * 2 + dp[i-8] * 2 + dp[i-10] * 2 + ...

 

 dp[i] =  dp[i-2] * 3 + ( dp[i-4] + dp[i-6] + dp[i-8]  + dp[i-10] + ... ) * 2

 

 

 

크기가 n인 도형이라면

• (n - 2) 크기 도형에 오른쪽 2크기를 붙이는 방법이 3가지가 있다.
  • dp[ n - 2 ] * 3
• 4이상인 짝수 크기 도형에서 각각 2가지 경우의 수씩 더 있다.
  • 4 크기 도형:  2개
  • 6 크기 도형:  2개
  • 8 크기 도형:  2개
  • ....
  • 그러므로,
  • (n - 4) 크기 도형에 오른쪽 4크기를 붙이는 방법:  2가지
  • (n - 6) 크기 도형에 오른쪽 6크기를 붙이는 방법:  2가지
  • (n - 8) 크기 도형에 오른쪽 8크기를 붙이는 방법:  2가지
  • ....
  • 결과적으로, dp[i - 4] * 2 + dp[i - 6] * 2 + dp[i - 8] * 2 + dp[i - 10] * 2 + ...

 

---

 

 

정답코드

 

#include <vector>
#include <cmath>
using namespace std;

const int MOD = 1000000007;

vector<long long> dp;

int solution(int n) {
    if (n % 2 == 1) return 0; // n이 홀수인 경우, 직사각형을 완전히 채울 수 없으므로 0 반환

    dp.resize(n + 1);
    dp[1] = 0;
    dp[2] = 3;
    dp[3] = 0;
    dp[4] = 11;

    dp[0] = 1; // 계산 편의를 위해 dp[0]을 1로 설정. n=4인 경우, 2가지 경우를 더해야 하는데 sum * 2 = 2 되어야 하므로 초기값을 1로 넣어줌.
    long long sum = 0;

	// dp[i] = dp[i-2]*3 + dp[i-4]*2 + dp[i-6]*2 + dp[i-8]*2 + dp[i-10]*2 + ...
    for (int i = 4; i <= n; i += 2)
    {
        sum += dp[i - 4];
        sum %= MOD;

        dp[i] = (dp[i - 2] * 3 + sum * 2) % MOD;
    }

    return dp[n];
}

int main(){
    cout << solution(4) << "\n"; // 11
    cout << solution(6) << "\n"; // 41
    cout << solution(8) << "\n"; // 153
    cout << solution(10) << "\n"; // 571
    cout << solution(12) << "\n"; // 2131
    cout << solution(14) << "\n"; // 7953

	return 0;
}

 

---