[백준 11727] 2×n 타일링 2_dp(c++)

[문제]

https://www.acmicpc.net/problem/11727

11727번: 2×n 타일링 2

[접근법]

• 다이나밍프로그래밍이란걸 보자마자 느낌..!
• 점화식을 찾아내기 위해 애썼음

[문제풀이]

• 고민하다가 찾은 점화식은

//홀수인경우
		if (i % 2 != 0) {
			memo[i] = ((memo[i-1] * 2) - 1) % 10007;
		}
		else {
			memo[i] = ((memo[i -1] * 2) + 1) % 10007;
		}

• 근데 알고보니 원리가 따로있었다
• 경우의 수는 가로가1인 경우와, 가로가2인경우(2x2 사용하거나 2x1) 두가지이다.
• 가로가 1인 경우의 개수 + 가로가 2인경우의 개수 * 2를 한 값을 dp에 저장해 두면 되는거였음
• 이런식이라면 3n타일링도 금방 점화식을 찾을 수 있을것같다!

for(int i = 2; i < n; i++){ // 타일의 가로 길이 1 or 2 -> n-1, n-2 이용 / n-2의 경우의 수 2*1와 2*2, 2개 이므로 *2 필요
		dp[i] = (dp[i-1] + ((dp[i-2]) * 2) % 10007) % 10007;
	}

 

[전체코드] 

#include <iostream>
using namespace std;
int memo[1001];
 
void dp(int n) {
    for (int i = 2; i <= n; i++) {
        //홀수인경우
        if (i % 2 != 0) {
            memo[i] = ((memo[i-1] * 2) - 1) % 10007;
        }
        else {
            memo[i] = ((memo[i -1] * 2) + 1) % 10007;
        }
    }
}
 
int main() {
    int n;
    cin >> n;
    memo[1] = 1; //1가지밖에 없음
 
    dp(n);
    //for(int i = 1; i<=n; i++)
    cout << memo[n] % 10007;
    
 
    return 0;
}