Search

BOJ 11726 2xn 타일링

태그
다이나믹 프로그래밍

문제 설명

•
2×N2 \times N 크기의 직사각형을 1×21 \times 2, 2×12 \times 1 타일로 채우는 방법의 수를 구하는 문제
◦
채우는 방법의 수를 10,007로 나눈 나머지를 출력

예제 입력/출력

•
입력1
2
Plain Text
복사
•
출력1
2
Plain Text
복사
•
입력2
9
Plain Text
복사
•
출력2
55
Plain Text
복사

제약 조건

•
1≤n≤1,0001 ≤ n ≤ 1,000

문제 풀이

풀이1 브루트 포스 - O(2N)O(2^N)
풀이2 그리디
풀이3 DP - O(N)O(N)

풀이 코드

•
Bottom-Up 방식의 구현
# input N = int(input()) # solve dp = [0] * (N + 2) dp[1] = 1 dp[2] = 2 for n in range(3, N + 1): dp[n] = (dp[n-1] + dp[n-2]) % 10007 print(dp[N])
Python
복사
Top-Down 방식의 구현

알아두면 좋은 내용들

답을 3214325(어떤 수)로 나눈 나머지를 출력하라 의 의미