[백준 온라인 저지] 14852. 타일 채우기 3

2*n 크기의 직사각형을 1*2, 2*1, 1*1 타일로 채우려고 한다.

 

1. 입력

- 첫째 줄에 n이 주어진다. (1 ≤ n ≤ 1,000,000)

- n이 직사각형의 가로다.

 

2. 출력

- 첫째 줄에 2×n 크기의 직사각형을 채우는 방법의 수를 1,000,000,007로 나눈 나머지를 출력한다.

 

3. 예제

 

4. 코드

1) 잘 안풀려서 제시된 c++ 코드를 java로 바꿔서 돌려본 코드

import java.util.*;
class Main{
    public static void main(String[] args){
        int n = new Scanner(System.in).nextInt();
        long[] d = new long[n+1];
        System.out.print(dp(n, d));
    }
    
    static long dp(int x, long[] d){
        if(x==0) return 1;
        if(x==1) return 2;
        if(x==2) return 7;
        if(d[x]>0) return d[x];
        d[x] = (3*dp(x-2, d) + 2*dp(x-1, d))%1000000007L;
        for(int i=3 ; i<=x ; i++)
            d[x] += (2*dp(x-i, d))%1000000007L;
        return d[x];
    }
}

- 가로를 n-2까지 채웠다고 했을 때 나머지 2를 채우는 경우의 수는 3가지가 있다. 가로 n-1까지 채웠다고 했을 때 나머지 1을 채우는 경우의 수는 2가지가 있다. n이 3 이상일 때 1씩 증가할때마다 고유한 모양이 2가지가 나타난다.

- 따라서 점화식을 쓰면 d[i] = 2*d[i-1] + 3*d[i-2] + 2*(d[i-3] + d[i-4] + ... + d[0])

- 이 코드는 백준에서 무조건 시간초과가 나오게 되어있다.

 

2) 재귀 함수 없이 구현한 코드

import java.util.*;
class Main{
    public static void main(String[] args){
        int n = new Scanner(System.in).nextInt();
        if(n==1)
            System.out.print(2);
        else if(n==2)
            System.out.print(7);
        else{
            long[] d = new long[n+1];
            d[0] = 1; d[1] = 2; d[2] = 7;
            for(int i=3 ; i<=n ; i++){
               d[i] = (2*d[i-1] + 3*d[i-2])%1000000007L;
               for(int j=3 ; j<=i ; j++)
                   d[i] += (2*d[i-j])%1000000007L;
            }
            System.out.print(d[n]);
        }
    }
}

- 이 역시 백준에서 시간초과가 난다.

 

3) 2차원 배열을 활용한 제시된 c++ 코드를 java로 바꿔서 돌려본 코드

import java.util.*;
class Main{
    public static void main(String[] args){
        int n = new Scanner(System.in).nextInt();
        if(n==1)
            System.out.print(2);
        else if(n==2)
            System.out.print(7);
        else{
            long[][] d = new long[n+1][2];
            d[0][0] = 1; d[1][0] = 2; d[2][0] = 7;
            // d[i][1]에 = d[i-3] + d[i-4] + ... + d[0] 저장
            for(int i=3 ; i<=n ; i++){
               d[i][1] = (d[i-1][1] + d[i-3][0])%1000000007L;
               d[i][0] = (2*d[i-1][0] + 3*d[i-2][0] + 2*d[i][1])%1000000007L;               
            }
            System.out.print(d[n][0]);
        }
    }
}

- 이해하는 데 시간도 오래 걸렸고, 1000000007로 나눈 나머지인데 모르고 0을 하나 더 붙여 찾아내는 게 더 힘들었다.