728x90
문제
2×n 크기의 직사각형을 1×2, 2×1 타일로 채우는 방법의 수를 구하는 프로그램을 작성하시오.
아래 그림은 2×5 크기의 직사각형을 채운 한 가지 방법의 예이다.
입력
첫째 줄에 n이 주어진다. (1 ≤ n ≤ 1,000)
출력
첫째 줄에 2×n 크기의 직사각형을 채우는 방법의 수를 10,007로 나눈 나머지를 출력한다.
풀이
dp[i] : 2xi 크기의 타일을 채우는 모든 경우의 수
n = 1 일때 1 : 2x1
n = 2 일때 2 : 2x1, 1x2
n >= 3 부터는 2x1 또는 1x2를 추가하는 경우에 대한 점화식이 성립한다.
2x1을 추가하는 경우에는 dp[i - 1]을, 1x2를 추가하는 경우에는 dp[i - 2]의 값을 활용하면 된다.
dp[i] = dp[i - 1] + dp[i - 2]
문제 조건에 따라 MOD(10,007)로 나눈 값을 dp에 담아주자.
소스코드
출처
728x90
'PS > Baekjoon Online Judge' 카테고리의 다른 글
[백준 11559] Puyo Puyo [Python] (1) | 2024.07.22 |
---|---|
[백준 11659] 구간 합 구하기 4 [Java] (0) | 2024.07.21 |
[백준 06378] 디지털 루트 [Java] (0) | 2024.07.21 |
[백준 01149] RGB거리 [C/C++] (2) | 2024.07.20 |
[백준 06322] 직각 삼각형의 두 변 [Python] (0) | 2024.07.20 |