백준 11727번. 2*n 타일링2

문제 링크

백준 11727번. 2*n 타일링2

프로그래머스. 2 x n 타일링

프로그래머스 문제는 살짝 다르다. 푸는 방법은 똑같다

1. 문제

2×n 직사각형을 1×2, 2×1과 2×2 타일로 채우는 방법의 수를 구하는 프로그램을 작성하시오.

아래 그림은 2×17 직사각형을 채운 한가지 예이다.

2. 입력

• 첫째 줄에 n이 주어진다. (1 ≤ n ≤ 1,000)

3. 출력

• 첫째 줄에 2×n 크기의 직사각형을 채우는 방법의 수를 10,007로 나눈 나머지를 출력한다.

4. 풀이

• dp 문제고 책에도 있어서 금방 풀었다.
• n-1칸까지 가득 차있다고 했을 때 채울 수 있는 경우는 1가지
• n-2칸까지 가득 차있다고 했을 때 채울 수 있는 경우는 2가지
• 점화식으로 쓰면 arr[n] = arr[n-1] + arr[n-2]*2

5. 처음 코드와 달라진 점

• 없음...

6. 코드

6-1. 백준

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

int arr[1000] = { 0 };

int main() {
	int n;
	cin >> n;
	
	arr[0] = 1;
	arr[1] = 3;
	
	for (int i = 2; i < n; i++){
		arr[i] = (arr[i - 1] + arr[i - 2] * 2)%10007;
	}

	cout << arr[n - 1] << endl;
}

6-2. 프로그래머스

#include <vector>

using namespace std;

int solution(int n) {
    int d[60000];
    d[0] = 1;
    d[1] = 2;
    
    for(int i=2; i<n; i++){
        d[i] = (d[i-1] + d[i-2])%1000000007;
    }
    
    return d[n-1];
}