[C++] 백준 11727번 : 2×n 타일링 2(S3)

#문제

www.acmicpc.net/problem/11727

11727번: 2×n 타일링 2

 

#풀이 & 학습한 내용

기존 2×n 타일링 문제에서 마지막에 올 수 있는 경우가 하나 추가된 문제이다. 타일의 마지막은 2x1타일 하나, 1X2타일 2개, 2X2타일 1개가 가능하다. 각각에 따른 문제는 같은 문제로 사이즈만 n-1, n-2, n-2일때와 같다. dp배열의 초기값으로 n=1일 때 1, n=2일 때 3을 넣어줬다. 그리고 dp[i] = (dp[i - 1] + 2 * dp[i - 2])를 통해 for문으로 순차적으로 dp[n]까지 계산한다.

 

#소스코드

#include<iostream>
#include<algorithm>
 
using namespace std;
 
int dp[1002];
 
int main(void) {
    int N;
    cin >> N;
    dp[1] = 1; dp[2] = 3;
    for (int i = 3; i <= N; i++) {
        dp[i] = (dp[i - 1] + 2 * dp[i - 2]) % 10007;
    }
    cout << dp[N] << "\n";
}

 

github.com/HoYoungChun/BOJ_algorithm/blob/master/Dynamic_Programming/BOJ_11727.cpp

HoYoungChun/BOJ_algorithm