BJ G1 13976 타일채우기 2

BJ G1 13976 타일채우기 2

 

 

문제링크

http://https://www.acmicpc.net/problem/13976

13976번: 타일 채우기 2

* 일단 문제를 정독 하고 1시간 이상 반드시 고민이 필요합니다.

 

동영상 설명

1시간 이상 고민 했지만 아이디어가 떠오르지 않는다면 동영상에서 약간의 힌트를 얻어봅시다.

https://youtu.be/-fsk0t6Ezk0

 

 

소스 보기

동영상 설명을 보고도 전혀 구현이 안된다면 이건 연습 부족입니다.
소스를 보고 작성해 본 후 스스로 백지 상태에서 3번 작성해 볼 의지가 있다면 소스를 살짝 보세요.

package bj.gold.g1;

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

/**
 * @author itsmeyjc
 * @since 2020. 4. 18.
 * @see https://www.acmicpc.net/problem/13976
 * @mem 12908
 * @time 76
 * @caution
 * f(n) = 4*f(n-2)-f(n-4)를 구한 후 행렬 식으로 변경해서 f(n) = ((4, -1),(1,0))^(n/2-1) * (f(2), f(0)) 로 유도
 * 이후 분할 정복으로 행렬의 제곱을 구해서 처리
 * Mod 연산 시 -가 나오는 경우를 대비해 M을 더한 후 나머지 연산할 것
 */
public class BJ_G1_13976_타일채우기2_DP {

    static long N; // 1 ≤ N ≤ 1,000,000,000,000,000,000 이만큼의 배열은 못만든다.
    static long M = 1000000007;

    public static void main(String[] args) throws IOException {

        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        br = new BufferedReader(new StringReader(src));
        N = Long.parseLong(br.readLine());

        if (N % 2 != 0) {
            System.out.println(0);
        } else {
            long[] baseCase = {3, 1};// d[2], d[0]
            if (N == 2) {
                System.out.println(3);
            } else {
                System.out.println(multiMatrix(getPower(new long[][] {{4, -1}, {1, 0}}, N / 2 - 1), baseCase));
            }
        }
    }

    /**
     * 분할 정복을 이용해서 제곱수 빠르게 구하기 - log n 처리
     * 
     * @param matrix
     * @param n
     * @return
     */
    static long[][] getPower(long[][] matrix, long n) {
        if (n == 1) {
            return matrix;
        } else {
            if (n % 2 == 0) {
                long[][] part = getPower(matrix, n / 2);
                return multiMatrix(part, part);
            } else {
                return multiMatrix(getPower(matrix, n - 1), matrix);
            }
        }
    }

    /**
     * 2차원 * 2차원 행렬의 곱 처리
     * 
     * @param a
     * @param b
     * @return
     */
    static long[][] multiMatrix(long[][] a, long[][] b) {
        long[][] multi = new long[2][2];
        multi[0][0] = getMod(a[0][0], b[0][0], a[0][1], b[1][0]);
        multi[0][1] = getMod(a[0][0], b[0][1], a[0][1], b[1][1]);
        multi[1][0] = getMod(a[1][0], b[0][0], a[1][1], b[1][0]);
        multi[1][1] = getMod(a[1][0], b[0][1], a[1][1], b[1][1]);
        return multi;
    }

    /**
     * 2차원 * 1차원 행렬의 곱 처리, 1차원 배열이 나오지만 거기서 d[n]에 해당하는 첫 번째 값만 필요하므로 그 녀석만 long으로 반환
     * 
     * @param a
     * @param b
     * @return
     */
    static long multiMatrix(long[][] a, long[] b) {
        return getMod(a[0][0], b[0], a[0][1], b[1]);
    }

    /**
     * 나머지 값 구할 때 음수가 나오는 경우에 대비해서 음수 쪽에는 M을 한번 더해주자.
     * 
     * @param a
     * @param b
     * @param c
     * @param d
     * @return
     */
    static long getMod(long a, long b, long c, long d) {
        // c*d가 음수일 경우를 대비해서 M을 더한 후 처리해주자.
        return ((a * b % M) + (c * d % M) + M) % M;
    }


    // static String src = "100";
    static String src = "4";

}