[종만북] ASYMTILING - 비대칭 타일링 (자바 java)

알고리즘 문제해결전략(종만북) 스터디 메인 페이지

목차

문제 : aoj-ASYMTILING

 

 

풀이

  일단 대칭인 경우는 생각하지 않고, 2xn 타일링부터 생각해보자. dp[x]를 x번째 열까지 타일을 높는 경우의 수라 하자.

이 경우 dp[5]의 경우 아래 그림처럼 dp[4]에 2x1 타일을 놓는 경우와, dp[3]에 1x2 타일 2개를 놓는 경우가 있을 것이다.

즉, dp[x] = dp[x-1] + dp[x-2] 로 구할 수 있다. 답은 dp[n]이 된다.

 

 

  그럼 다음으로 대칭인 경우를 제외해보자.

열이 홀수개일 경우 대칭인 경우는 이하처럼 중간에 2x1 타일이 있는 경우이다.

즉, dp[n]에서 dp[(n-1)/2] 를 빼주면 된다! (대칭인 경우를 빼면 되므로)

 

 

  열이 짝수개인 경우엔 다음의 두 가지 경우가 있다. 따라서 대칭되는 경우를 빼주면 dp[n] - dp[n/2] - dp[n/2-1] 이 답이 된다.

 

 

코드 : github

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

public class Main {
    static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    static StringBuilder sb = new StringBuilder();
    static final int MOD = 1000000007;

    public static void main(String[] args) throws Exception {
        int c = Integer.parseInt(br.readLine());
        while (c-->0) new Main().solution();
        System.out.print(sb);
    }

    private void solution() throws Exception {
        int n = Integer.parseInt(br.readLine());
        if (n <= 2) {
            sb.append(0).append('\n');
            return;
        }

        int[] arr = new int[n+1];
        arr[0] = 1;
        arr[1] = 1;
        arr[2] = 2;

        for (int i = 3; i <= n; i++) {
            arr[i] = (arr[i-2] + arr[i-1]) % MOD;
        }

        long answer = arr[n];
        if ((n%2==0)) {
            answer -= arr[n/2] + arr[n/2-1];
            answer += 2*MOD;
        } else {
            answer -= arr[(n-1)/2];
            answer += MOD;
        }

        answer%=MOD;

        sb.append(answer).append( '\n');
    }
}

 

 

※ 종만북에 이미 풀이가 있는데 제 풀이를 올리는 이유는 제가 책의 풀이를 보지 않고 문제를 푼 후 제 풀이를 올리고 나서 책의 풀이를 보는 방식으로 풀어보고 싶기 때문입니다.