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

#문제

www.acmicpc.net/problem/11726

11726번: 2×n 타일링

 

#풀이 & 학습한 내용

마지막에 타일이 올수 있는 경우는 1개가 서있는것과, 2개가 가로로 누워있는 것이다. 각각의 경우는 n-1과 n-2일 때의 문제를 푸는 것과 동일하므로 dp를 이용하여 앞에서부터 순차적으로 n까지 dp배열을 채워나간다. 이때 dp의 basis case는 n=1일 때 1과 n=2일 때 2이다. 또한, 문제에서 무언가로 나눈 답을 구하란 것을 문제를 푸는 과정에서 나누면서 구하라는 뜻이다.

 

#소스코드

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

 

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

HoYoungChun/BOJ_algorithm