반응형
https://www.acmicpc.net/problem/11727
11727번: 2×n 타일링 2
2×n 직사각형을 1×2, 2×1과 2×2 타일로 채우는 방법의 수를 구하는 프로그램을 작성하시오. 아래 그림은 2×17 직사각형을 채운 한가지 예이다.
www.acmicpc.net
[ 문제풀이 ]
이 문제는 간단한 점화식을 세워서 풀 수 있었습니다.
dp[ i ] = dp[ i - 1 ] + dp[ i - 2 ] * 2
[ 소스 코드 ]
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 | #include<iostream> using namespace std; int n; int dp[1001]; int main() { cin >> n; dp[1] = 1; dp[2] = 3; for (int i = 3; i <= n; i++) { dp[i] = dp[i - 1] + dp[i - 2] * 2; dp[i] %= 10007; } cout << dp[n]; } | cs |
반응형
'백준' 카테고리의 다른 글
| [ 백준 ] 11047번 - 동전 0 (C++) (0) | 2022.08.19 |
|---|---|
| [ 백준 ] 14889번 - 스타트와 링크 (C++) (0) | 2022.08.18 |
| [ 백준 ] 14499번 - 주사위 굴리기 (C++) (0) | 2022.08.16 |
| [ 백준 ] 3190번 - 뱀 (C++) (0) | 2022.08.15 |
| [ 백준 ] 7576번 - 토마토 (C++) (0) | 2022.08.14 |