끄적끄적
백준 11727 [2xn 타일링 2] -dp 본문
출처 : https://www.acmicpc.net/problem/11727
2×n 타일링 2
1 초 | 256 MB | 38908 | 23245 | 18427 | 59.279% |
문제
2×n 직사각형을 1×2, 2×1과 2×2 타일로 채우는 방법의 수를 구하는 프로그램을 작성하시오.
아래 그림은 2×17 직사각형을 채운 한가지 예이다.
입력
첫째 줄에 n이 주어진다. (1 ≤ n ≤ 1,000)
출력
첫째 줄에 2×n 크기의 직사각형을 채우는 방법의 수를 10,007로 나눈 나머지를 출력한다.
예제 입력 1
2
예제 출력 1
3
예제 입력 2
8
예제 출력 2
171
예제 입력 3
12
예제 출력 3
2731
출처
- 문제를 만든 사람: baekjoon
알고리즘 분류
11726과 규칙만 다르고 똑같은 문제다. (2*2 타일이 추가되었기 때문)
1->1
2->3
3->5
4->11
이므로 여기서 dp[i]=dp[i-1]+2*dp[i-2]의 규칙을 찾아 적용하여 풀었다.
'코테준비' 카테고리의 다른 글
백준 12100 [2048(Easy)] - dfs & 브루트포스 (0) | 2021.10.04 |
---|---|
프로그래머스 level 3 [징검다리 건너기] (0) | 2021.10.01 |
백준 11726 [2×n 타일링] -dp (0) | 2021.09.27 |
백준 2206 [벽 부수고 이동하기] -BFS (0) | 2021.09.23 |
백준 2579 [계단 오르기] - DP (0) | 2021.09.23 |