백준 11727번 (2×n 타일링 2, C++, DP) [BAEKJOON]
문제
https://www.acmicpc.net/problem/11727
| 시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
|---|---|---|---|---|---|
| 1 초 | 256 MB | 56506 | 33840 | 27060 | 59.291% |
2×n 직사각형을 1×2, 2×1과 2×2 타일로 채우는 방법의 수를 구하는 프로그램을 작성하시오.
아래 그림은 2×17 직사각형을 채운 한가지 예이다.
입력
첫째 줄에 n이 주어진다. (1 ≤ n ≤ 1,000)
출력
첫째 줄에 2×n 크기의 직사각형을 채우는 방법의 수를 10,007로 나눈 나머지를 출력한다.
예제 입력 1
plaintext
2예제 출력 1
plaintext
3예제 입력 2
plaintext
8예제 출력 2
plaintext
171예제 입력 3
plaintext
12예제 출력 3
plaintext
2731알고리즘 분류
cpp
#include <iostream>
using namespace std;
long long int arr[1001];
constexpr int MOD = 10007;
int main()
{
ios_base::sync_with_stdio(false); // scanf와 동기화를 비활성화
// cin.tie(null); 코드는 cin과 cout의 묶음을 풀어줍니다.
cin.tie(NULL);
cout.tie(NULL);
cin >> arr[0];
// DP 배열초기화
arr[1] = 1;
arr[2] = 3;
for (int i = 3; i <= arr[0]; i++)
arr[i] = (arr[i - 1] % MOD + (arr[i - 2] * 2) % MOD) % MOD; // 모듈러 산술
cout << arr[arr[0]];
return 0;
}