개발일지/Algorithm
백준 - 11726 2×n 타일링 [DP]
E-room
2023. 10. 12. 13:37
728x90
11726번: 2×n 타일링
2×n 크기의 직사각형을 1×2, 2×1 타일로 채우는 방법의 수를 구하는 프로그램을 작성하시오. 아래 그림은 2×5 크기의 직사각형을 채운 한 가지 방법의 예이다.
www.acmicpc.net
1. 문제 요약
2×n 크기의 직사각형을 1×2, 2×1 타일로 채우는 방법의 수를 구하시오.
2. 접근 방법
숨어있는 규칙을 찾아봅시다.
i : 방법
1 -> 1
2 -> 2
3 -> 3
4 -> 5
5 -> 8
6 -> 13
7 -> 21자세히 살펴보면 규칙을 발견할 수 있습니다.
현재 인덱스의 방법은 이전의 두 인덱스의 방법의 합과 같습니다.
즉, n = (n-1) + (n-2) 가 됩니다.
이는 피보나치 수열의 형태입니다.
이를 토대로 재귀함수를 이용합니다.
def solution(n:int):
if n <= 2:
return n
return solution(n-1) + solution(n-2)
다만 해당 코드는 시간초과가 발생하므로 최적화를 진행해야 합니다.
3. 파이썬
def solution(n:int):
dp = [1, 2]
for i in range(3, n+1):
dp.append(dp[i-2] + dp[i-3])
print(dp[n-1] % 10007)
4. 자바
static private int solution(int n) {
int[] dp = new int[n];
dp[0] = 1;
if (n > 1) {
dp[1] = 2;
}
for (int i = 2; i < n; i++) {
dp[i] = (dp[i - 1] + dp[i - 2]) % 10007;
}
return dp[n - 1];
}
5. 전체 코드
728x90