[ DP ] 바닥 공사

난이도 : 중하  풀이시간 : 20분  시간제한 : 1초

[ DP ] 바닥 공사

가로의 길이가 N, 세로의 길이가 2인 직사각형 형태의 얇은 바닥이 있다. 태일이는 이 얇은 바닥을 1 X 2의 덮개, 2 X 1의 덮개, 2 X 2의 덮개를 이용해 채우고자 한다. 이 때 바닥을 채우는 모든 경우의 수를 구하여라.

 

:: 입력 조건

 

• 첫째 줄에 N이 주어진다.(1 <= N <= 1,000)

 

:: 출력 조건

 

• 첫째 줄에 2 X N 크기의 바닥을 채우는 방법의 수를 796,796으로 나눈 나머지를 출력한다.

 

---

 

  내   코드  

#include <iostream>
#include <vector>
#include <algorithm>
#include <string>

using namespace std;

#define endl "\n"

int dp[1001];

int x;

int main() {
	cin >> x;

	dp[0] = 0;
	dp[1] = 1;
	dp[2] = 3;

	for (int i = 3; i <= x; i++) {
		dp[i] = (dp[i - 1] + dp[i - 2] * 2) % 796796;
	}

	cout << dp[x] << endl;

}

 

  정답  코드  

#include <bits/stdc++.h>

using namespace std;

// 앞서 계산된 결과를 저장하기 위한 DP 테이블 초기화
int d[1001];
int n;

int main(void) {
    // 정수 N을 입력받기
    cin >> n;

    // 다이나믹 프로그래밍(Dynamic Programming) 진행(보텀업)
    d[1] = 1;
    d[2] = 3;
    for (int i = 3; i <= n; i++) {
        d[i] = (d[i - 1] + 2 * d[i - 2]) % 796796;
    }

    // 계산된 결과 출력
    cout << d[n] << '\n';
}

 

  리뷰  

공식 비슷하게 생각했는데 틀림 ,, 

다시 풀어보기 !