[DP] 3열 타일 채우기 + pro문제 타일 채우기

www.acmicpc.net/problem/2133

2133번: 타일 채우기

제일 BASE 한 문제는 이것이다.

 

d[2] = 3

d[4] = d[2]*3 + 2

d[6] = d[4]*3 + d[2] * 2 + 2

d[8] = d[6] * 3 + d[4]* 2 + d[2] * 2 + 2..

이기 때문에 

import java.util.*;
import java.io.*;
import java.math.*;
 
public class D210412_jungol2112_세줄로타일깔기 {
 
    static int n;
 
    public static void main(String[] args) throws IOException {
        //System.setIn(new FileInputStream("input.txt"));
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        
        int[] d = new int[31];
        
        d[2] = 3;
        
        for(int i = 4 ; i <= 30 ; i+=2) {
            d[i] += (d[i-2] * 3);
            for(int j = i-4 ; j >= 2 ; j-=2)
                d[i] += (d[j]*2);
            d[i] += 2;
        }
    
        int n = Integer.parseInt(br.readLine());
        
        System.out.println(d[n]);
        
    }
}
 

이런 스탠스를 취하면 된다.

 

 

 

 

 

BUT N의 제한사항이 100만이라면 이것을 어떻게 풀것인가????

위에대로 풀면 n^2가 나올텐데 말이다.

정답은 sum[] 을 이용해보자.

 long[] d = new long[1000001];
 long[] sum = new long[1000001];
 d[0] = 1;    sum[0] = 1;

 

  for (int i = 2; i <= N; i += 2) {
        d[i] = (d[i - 2] + sum[i - 2] * 2)%mod;
        sum[i] = (sum[i - 2] + d[i])%mod;
    }

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

이제 이것을 갖고 다음의 PRO 문제를 풀어보자.

 

문제

높이가 3, 너비가 N인 벽이 있다. N은홀수이며 이 벽을 1*2 크기의 타일로 빈틈없이 채우고자 한다. 단, 이 벽에는 한 칸의 빈 공간이 있어서 해당 공간만 빼고 모든 공간을 채워야 한다.

타일의 방향은 가로, 세로 상관없다.

벽의 너비와 빈 공간의 좌표가 주어질 때 타일로 벽을 꽉 채울 수 있는 모든 경우의 수를 구하여라.

 

Ex.

 

 

입력.

입력의 첫 줄에는 테스트 케이스의 개수 T가 주어진다.

그 다음 줄부터 각각의 테스트 케이스에 대해 정수 N과 빈 공간의 좌표 X, Y가 주어진다.
(1≤N≤1000000, 1≤X≤N, 1≤Y≤3)

 

출력

각 테스트 케이스에 대해 출력한 값을 100000007로 나눴을 때의 나머지 값을 출력한다.

(제한시간 1.5초)

 

 

Input

7

5 3 3

7 4 2

11 5 1

51 4 1

1385 1 1

9999 7451 3

542153 245672 2

 

 

Output

#1 15

#2 32

#3 780

#4 0

#5 446155318

#6 196872679

#7 840796139

 

 

 

 

 

일단 타일에 빈공간 따른 경우의 수를 구해보자.

 

 

 

 

 

 

 

 

 

 

 

 

그럼 이것을 토대로 알고리즘을 만들어보자.

 

 

import java.util.*;
import java.io.*;
import java.math.*;
 
public class D210413_pro181013_타일채우기 {
 
    static final long mod = 1000000007;
 
    public static void main(String[] args) throws IOException {
        //System.setIn(new FileInputStream("input.txt"));
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        
        long[] arr = new long[1000001]; // 
        long[] sum = new long[1000001]; // sum[8] = ( arr[0] + arr[2] + arr[4] + arr[6] + arr[8])
    
        arr[0] = 1;
        sum[0] = 1;
 
        for (int i = 2; i <= 1000000; i += 2) {
            arr[i] = (arr[i - 2] + sum[i - 2] * 2)%mod;
            sum[i] = (sum[i - 2] + arr[i])%mod;
        }
        
        /*
        for(int i = 2 ; i <= 50 ; i+=2)
        {
            System.out.println(arr[i] + " " + (sum[i]));
        }
        */
        
        int tc = Integer.parseInt(br.readLine());
        for(int z = 1 ; z <= tc ; z++) {
            StringTokenizer st = new StringTokenizer(br.readLine());
            int n = Integer.parseInt(st.nextToken());
            int x = Integer.parseInt(st.nextToken());
            int y = Integer.parseInt(st.nextToken());
            
            //7 4 2
            if(y == 2) {
                if(x%2 == 0) {
                    int left = x-2;
                    int right = n - (x+1);
                    long ans = 0;
                    
                    for(int i = left ; i >= 0 ; i-= 2)
                        ans = (ans + (2 * arr[i] * (sum[right])))%mod;
                    System.out.println("#"+z+" "+ans);
                }
                else
                    System.out.println("#"+z+" "+0);
            }
            // 5 3 3
            if(y == 1 || y == 3) {
                if(x%2 == 1) {
                    int left = x-1;
                    int right = n-x;
                    long ans = arr[left]*arr[right]%mod;
                    if(right >= 2)
                        ans = (ans + arr[left]*(sum[right-2]))%mod;
                    if(left >= 2)
                        ans = (ans + arr[right]*(sum[left-2]))%mod;
                    System.out.println("#"+z+" "+ans);
                }
                else
                    System.out.println("#"+z+" "+0);
            }
            
        }
 
    }
}