[백준 11726] 2xn 타일링 c++

문제 링크 : 백준 11726 2xn 타일링

문제

2xn 크기의 직사각형을 1x2, 2x1 타일로 채우는 방법의 수를 구하는 프로그램을 작성하시오.

• 예시
  • 입력 : 2 / 출력 : 2
  • 입력 : 9 / 출력 : 55

풀이

Bottom-up 방식의 DP. 규칙을 찾고 점화식을 세워 해결하는 방식이다. 그림을 그려보며 규칙을 찾아낸다. cache 배열에 3번째 인덱스까지의 값을 초기화 해준다. 내가 살짝 헤맸던 부분은 cache[i] 번째에 일단 i-1 번째 인덱스와 i-2번째 인덱스를 더해주고 나중에 답을 구할 때 10007 modulo 계산을 해주어 출력을 한 부분이 왜 오답인지 몰랐어서 헤맸다. 다시 생각해보니 반복문 안에서 modulo 연산을 해주지 않으면 이전 값이 전부 틀려버리기 때문에 반복문 안에서 연산을 해주며 i번째에 넣어주어야 하는게 맞다.

코드

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

int cache[1000];

int main() {
    cout << "start" << endl;
    int n;
    cin >> n;

    cache[1] = 1;
    cache[2] = 2;
    cache[3] = 3;

    for(int i = 4; i <= n; i++) {
        cache[i] = (cache[i-1] + cache[i-2]) % 10007;
    }

    cout << cache[n] << endl;

    return 0;
}