개요
- 동적 계획법을 활용하는 알고리즘 문제를 풀어보고, 기록을 남겨두는 페이지
1. 문제
"""
백준 11726번
2×n 타일링
- 시간 제한 메모리 제한 제출 정답 맞힌 사람 정답 비율
1 초 256 MB 102196 38576 28196 35.485%
- 문제
2×n 크기의 직사각형을 1×2, 2×1 타일로 채우는 방법의 수를 구하는 프로그램을 작성하시오.
- 입력
첫째 줄에 n이 주어진다. (1 ≤ n ≤ 1,000)
- 출력
첫째 줄에 2×n 크기의 직사각형을 채우는 방법의 수를 10,007로 나눈 나머지를 출력한다.
"""
2. 접근 방법 및 구현
- n이 1인 경우부터 하나씩 증가시켜보며, 패턴이 있는지 확인해본다.
- 각 단계 사이의 관계를 점화식으로 표현할 수 있는지 확인해본다.
- 이 문제에서는 현재 단계는 이전 두 단계의 Case를 합친 결과이다.
n = int(input())
dp_table = [0 for i in range(1001)]
dp_table[1] = 1
dp_table[2] = 2
for i in range(3, 1001):
dp_table[i] = dp_table[i - 1] + dp_table[i - 2]
answer = dp_table[n - 1] % 10007
print(answer)