목록2025/04/23 (1)

넘치게 채우기

[BOJ] 13976 - 타일 채우기 2

https://www.acmicpc.net/problem/13976BOJ - 타일 채우기 2문제 유형: 다이나믹 프로그래밍, 분할 정복, 수학문제 난이도: Platinum V시간 제한: 2초메모리 제한: 512MB 문제3×N 크기의 벽을 2×1, 1×2 크기의 타일로 채우는 경우의 수를 구해보자. 입력첫째 줄에 N(1 ≤ N ≤ 1,000,000,000,000,000,000)이 주어진다. 출력첫째 줄에 경우의 수를 1,000,000,007로 나눈 나머지를 출력한다. 풀이3 x n을 1 x 2또는 2 x 1 타일로 채우는 경우의 수의 점화식은T(n) = 4 * T(n-2) - T(n-4)이다. T(n-4)를 유도하기 위해서, T(n-6)까지가 필요하다 (n >= 8부터) T(n), T(n-2), T(n-4..
PS/BOJ 2025. 4. 23. 23:56
이전 Prev 1 Next 다음