백준 11727 2xn 타일링 2, c++

 

 

 

처음 작성한 코드는 다음과 같다.

2xn 배열상에서, i번째 인덱스에서,

발생할 수 있는 경우의 수는 다음과 같다고 생각하여

이를 기반해 알고리즘을 구현했다.

#include <iostream>
using namespace std;

int main(){
    int n;
    cin >> n;
    
    int dp[n+1];
    dp[1] = 3;
    dp[2] = 5;
    dp[3] = 11;
    int temp = 5;
    
    for(int i=4; i<=n; i++){
        dp[i] = temp + temp + (temp+3+3);
        temp = (temp+3+3);
    }
    
    cout << dp[n] % 10,007;
    return 0;
}

 

 

 

하지만 틀렸다는 결과가 나왔다.

계속 이어지는 경우에는 2x2, 2x1을 선택해도 되지만, 배열의 마지막인 경우에는 새로운 2x2, 2x1을 시도하면 안된다는 점을 고려하지 못한 것이었다.

위와 의미는 같은 알고리즘이나 약간 표현방식을 달리 해야했다.

#include <iostream>
using namespace std;

int main(){
	int N;
	cin >> N;
    
    int dp[1001];
	dp[1]=1; dp[2]=3; dp[3]=5; dp[4]=11;
    
	for(int i=5; i<=N; i++){
		dp[i]=(dp[i-1]+dp[i-2]*2) % 10007;
	}
    
	cout<<dp[N];
    return 0;
}