[BOJ][실3][11727] 2 X n 타일링2

문제 링크

문제링크

첫 번째 풀이 : DP

알고리즘

가장 오른쪽 칸을 채우는 방법은 1x2 1개를 사용하거나 2x1 2개를 사용하거나 2x2 1개를 사용하는 방법 뿐입니다.

dp[i] = dp[i-1] + 2 * dp[i-2]

정답코드

#include <bits/stdc++.h>
using namespace std;

using ll = long long;
using pii = pair<int, int>;

const int MAX = 1001;
const int MOD = 10007;
int arr[MAX][MAX];
int dp[MAX];
bool visited[MAX][MAX];

int dx[4] = { 0,0,1,-1 };
int dy[4] = { 1,-1,0,0 };

int n, m;

void show(void);
void bfs(int x, int y);

int main()
{
  //freopen("input.txt", "r", stdin);
  ios_base::sync_with_stdio(0); cin.tie(0);
  cin >> n;
  dp[0] = 0;
  dp[1] = 1;
  dp[2] = 2;
  for (int i = 3; i <= n; i++) {
    dp[i] += dp[i - 2];
    dp[i] %= MOD;
    dp[i] += dp[i - 1];
    dp[i] %= MOD;
  }
  cout << dp[n];


  return 0;
}

Success Notice: 수고하셨습니다.