[알고리즘-JAVA] 백준 알고리즘 11727번 - 2*n 타일링 2

접근 과정
1. 어떤 문제로 이해 했는가? 그리고 문제의 제약 조건은?

2*n 직사각형을 2*1, 1*2, 2*2 타일로 채우는 방법의 수를 구하는 문제이다.

2. 나의 방식대로 문제를 재정의 하자.
d[n] = 2*n 직사각형을 타일로 채우는 방법의 수.

d[n]을 점화식 형태로 표현해 내기.

3. 어떤 알고리즘과 자료구조를 사용할 것인가?

재귀함수 (Top-down)이나 반복문(Bottom-UP)을 사용할 계획이다.

4. 어떻게 계산할 것인가?
1) 입력

BufferedReader를 사용해 입력받을 것이다.

 

2) 시간 복잡도 계산

최악 = O(N) (d[n]까지 n번 계산)

 

5. 주의할 점은 무엇인가?

방법의 수를 10007로 나눈 나머지를 구해야한다.

 

6. 풀이 과정

 

 

전체 소스 코드

Top-Down

크게 달라진건 없고, 이전 2*n 문제에서

d[length] = calculate(length-2)블럭이 하나 더 추가되었다는 점이다.

length-2인 이유는 2*2 블럭이기 때문에 왼쪽에 남는 여백의 가로길이가 n-2이기 때문이다.

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.io.IOException;

public class Main{
    static long d[];
        
    public static void main(String args[]) throws IOException{
        BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
        int length = Integer.parseInt(bf.readLine());
        d = new long[length+1];
        System.out.println(calculate(length));
    };

    static long calculate(int length){
        if (length == 0 || length == 1){
            return 1;
        }
        if (d[length] > 0) return d[length];

		// calculate(length-2) 하나 더 추가 for 2*2 block
        d[length] = calculate(length-1) + calculate(length-2) + calculate(length-2);
        d[length] %= 10007;
        return d[length];
    }
}

Bottom-Up

이 역시 크게 달라진 것 없이 d[length]를 구하는 부분을 추가해 주면 된다.

아래의 코드를 보면 d[i] = d[i-1] + d[i-2] + d[i-2]로 구하는 것을 알 수 있다.

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.io.IOException;

public class Main{
    public static void main(String args[]) throws IOException{
        BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
        int length = Integer.parseInt(bf.readLine());

        //bottom-up
        int d[] = new int[length+1];
        d[0] = 1;
        d[1] = 1;
        for (int i = 2; i <= length; i++){
        // 추가된 부분 : d[i-2] for 2*2 block
            d[i] = d[i-1] + d[i-2] + d[i-2];
            d[i] %= 10007;       
        }
        System.out.println(d[length]);
    };
}