[백준] 2xn 타일링 in Java

📍 문제

https://www.acmicpc.net/problem/11726

📍 코드 설명

2 * n 의 직사각형을 2 * 1 or 1 * 2 의 직사각형으로 채울 때 가능한 경우의 수를 찾는 문제

 

이 때 결국 1 * n개의 직사각형을 1 * 1 or 1 * 2의 직사각형으로 채울 때와 동일하므로 결국 배열을 2칸 채우냐, 1칸 채우냐로 생각하면 편하다.

일단 어떻게 풀어야할지 감이 오지 않으므로 5개 까지는 손으로 직접 구해본다

 

n = 1

경우의 수 1 => 1개

 

n = 2

경우의 수 11 / 2 => 2개 

 

n = 3

경우의 수 111 / 12 / 21 => 3개

 

n = 4

경우의 수 1111 / 112 / 121 / 211 / 22 => 5개

 

n = 5

경우의 수 11111 / 1112 / 1121 / 1211 / 2111 / 122 / 212 / 221 => 8개

 

규칙이 보인다

n의 경우의 수 = n -2개의 경우의 수 + n-1개의 경우의 수 이다

피보나치 수열과 동일한 패턴

 

주의할점

• n = 2이므로 dp [0] = dp [1] = 1로 두고 n = 2부터 n-2 + n-1을 적용한다
• 10007로 나누는 이유 : n이 조금만 커져도 결과값이 매우 커지기 때문에 결과값을 int로 구하기 위해서
  • dp[n] % 10007 = dp[n-2] % 10007 + dp[n-1] % 10007 과 동일하므로 dp[n]을 구할 때 10007로 나눈 값으로 저장한다

 

📍 코드

✔️ 코드

import java.util.*;

public class Main
{
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();

        int[] dp = new int[1001];
        dp[0] = 1;
        dp[1] = 1;

        System.out.println(fibonacci(dp, n));

    }

    static int fibonacci(int[] dp, int n){
        if(dp[n] != 0){
            return dp[n];
        }else{
            if(n == 0 || n == 1){
                return 1;
            }else{
                dp[n] = (fibonacci(dp, n -1) + fibonacci(dp, n -2)) % 10007;
            }
            return dp[n];
        }
    }
}

 

📍 기억할 것

감이 안오면 일단 손으로 써보면서 규칙을 찾아보자