# 생각
테이블 정의
d[i] = 2 × i 크기의 직사강형을 채우는 방법의 수
점화식
2×1 타일로 덮으면 k-1가지
1×2 타일로 덮으면 k-2가지가 있기 때문에
d[k] = d[k-1] + d[k-2]가 된다
초기값
d[k]를 구할 때 k-2 까지 필요하므로 d[1]과 d[2]를 초기값으로 둔다
# 전체 코드
#include <bits/stdc++.h>
using namespace std;
int d[1111];
int main()
{
ios::sync_with_stdio(false);
cin.tie(nullptr);
int n;
cin >> n;
d[1] = 1;
d[2] = 2;
for (int i = 3; i <= n; i++)
{ // 마지막에만 나머지 연산으로 출력하게 되면 int 오버플로우가 날 수 있다
d[i] = (d[i - 1] + d[i - 2]) % 10007;
}
cout << d[n];
}
https://www.acmicpc.net/problem/11726
11726번: 2×n 타일링
2×n 크기의 직사각형을 1×2, 2×1 타일로 채우는 방법의 수를 구하는 프로그램을 작성하시오. 아래 그림은 2×5 크기의 직사각형을 채운 한 가지 방법의 예이다.
www.acmicpc.net
'Algorithm > BOJ' 카테고리의 다른 글
[BOJ] 12852_1로 만들기 2 with cpp (0) | 2022.03.04 |
---|---|
[BOJ] 11659_구간 합 구하기 4 with cpp (0) | 2022.03.04 |
[BOJ] 1149_RGB거리 with cpp (0) | 2022.03.04 |
[BOJ] 9095_1,2,3 더하기 with cpp (0) | 2022.03.02 |
[BOJ] 1463_1로 만들기 with cpp (0) | 2022.03.02 |