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

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

2*n 크기의 직사각형을 채우는 방법의 수를 구하는 문제이며, n은 1~1000사이의 수이다.

2. 나의 방식대로 문제를 재정의 하자.
2*n 크기의 직사각형을 채우는 방법의 수를 점화식을 이용해서 구해내는데

이때 세로로 세워져 있는 경우와 가로로 누워 있는 경우를 모두 합쳐주면 된다.

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

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

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

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

 

2) 시간 복잡도 계산

n번째까지 계산을 해야하므로 O(N)

 

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

점화식을 제대로 구해내는 과정.

 

6. 풀이 과정

점화식을 구해내는 과정은.

가로의 길이가 n일때, 세로 1*2 블록을 하나 그리면 왼쪽에 남는 공간이 n-1개 블럭을 배치하는 경우가 남는다는 점을 이용했다.

마찬가지로 가로가 n일때, 가로 2*1블록을 가로로 2개 놓으면 왼쪽에 남는 공간이 n-2개 블럭을 배치할만큼 남는다는 점을 이용했고,

총 횟수는 두가지의 합, 즉 아래의 점화식으로 나타낼 수 있었다.

F(n) = F(n-1) + F(n-2)

 

처음에 짠 Bottom-UP은 런타임에러가 났었다. 근데 이상하게 아래의 코드는 성공했다.

d[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;
        d[2] = 2;
        for (int i = 3; i <= length; i++){
            d[i] = d[i-1] + d[i-2];
            d[i] %= 10007;       
        }
        System.out.println(d[length]);
    };
}

 

전체 소스 코드

Bottom-UP

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] = d[i-1] + d[i-2];
            d[i] %= 10007;       
        }
        System.out.println(d[length]);
    };
}

Top Down

탑다운도 바텀업처럼 한번에 성공하지 못했는데,

if (d[length] >0) return d[length] 구절을 안적었더니 굉장히 연산속도가 느렸다.

이미 계산한 코드를 다시 계산하기 때문에 그런것이다.

이런 사소한 부분도 꼼꼼하게 공부하는 습관 가져야지!

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];
        
        d[length] = calculate(length-1) + calculate(length-2);
        d[length] %= 10007;
        return d[length];
    }
}

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];
        
        d[length] = calculate(length-1) + calculate(length-2);
        d[length] %= 10007;
        return d[length];
    }
}