[백준/C++] 알고리즘 11727번 - 2×n 타일링 2

안녕하세요! 테크지니어22입니다.
오늘은 백준 알고리즘 11727번 - 2×n 타일링 2 를 풀어보도록 하겠습니다.
 
https://www.acmicpc.net/problem/11727

11727번: 2×n 타일링 2

 
[문제 접근]
패턴을 찾아내는 문제라고 생각하여 다이나믹 프로그래밍으로 접근하였습니다.
d[n]은 2xn타일링을 채우는 방법의 수라고 정의했습니다.
d[n+2] = d[n+1] + 2*d[n]이라는 점화식을 발견했습니다. 발견하는 과정은 그림과 같습니다.

 
[풀이 전략]
1. dp배열 초기값을 설정합니다.
2. for문을 돌면서 dp배열을 채워나갑니다. 저장할 때 10007 모듈러 연산을 실행합니다.
(모듈러 연산을 안하면 오버플로우 값이 배열에 저장되서 출력이 잘못나올 수 있습니다.)
 
[코드]

#include <iostream>
#include <algorithm>
using namespace std;


int n ; 
int d[1001] ;

int main() {
  ios::sync_with_stdio(0);
    cin.tie(0); 
    cin >> n ; 
    
    d[1] = 1 ;
    d[2] = 3 ;

    for(int i = 3 ; i <= n ; i++){
        d[i] = 2*(d[i-2]% 10007) + (d[i-1]% 10007);
    }

    cout << d[n];
}

 
[배울 점]
- 그림 그려보면서 패턴 발견하기.