백준 - 11726 2×n 타일링 [DP]

 

11726번: 2×n 타일링

 

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. 전체 코드

https://github.com/Ksiyeong/Algorithm/tree/main/%EB%B0%B1%EC%A4%80/Silver/11726.%E2%80%852%C3%97n%E2%80%85%ED%83%80%EC%9D%BC%EB%A7%81