[BOJ] 14852. 타일 채우기 3

[작성일]

• 2022-03-24

[분류]

• dp
  
  
  

[문제링크]

• https://www.acmicpc.net/problem/14852
  
  
  

[요구사항]

2×N 크기의 벽을 2×1, 1×2, 1×1 크기의 타일로 채우는 경우의 수를 구해보자.
경우의 수를 1,000,000,007로 나눈 나머지를 출력하자.

굉장히 어려운 문제였다고 생각한다.

• 두 가지 방법을 이용해서 풀어보았다.

[풀이1]

1. 현재 위치를 기준으로 어떻게 채워넣을 수 있는지 고민하는 방법

현재 위치를 n번째 위치라고 하면 채울 수 채울 수 있는 경우는 위의 그림과 같다.
이후 2차원 dp 배열을 사용하는데, i는 차례를, j은 해당 차례 두 칸을 얼마나 채우는지 여부에 따라서 0, 1, 2로 구분한다.

• j == 0 -> 두 칸 모두 채우는 경우
• j == 1 -> 위 칸만 채우는 경우
• j == 2 -> 아래 칸만 채우는 경우

이에 따라 dp 식을 세우고 구현해주면 답이 나온다.

[코드1]

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


class Main {
    static int N;
    static long[][] dp;
    static long MOD = 1000000007;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        N = Integer.parseInt(br.readLine());
        dp = new long[N][3];
        dp[0][0] = 2;
        dp[0][1] = 1;
        dp[0][2] = 1;

        if(N > 1) {
            dp[1][0] = 7;
            dp[1][1] = 3;
            dp[1][2] = 3;
        }

        for (int i = 2; i < N; i++) {
            dp[i][0] = (2 * dp[i - 1][0] + dp[i - 2][0] + dp[i - 1][1] + dp[i - 1][2]) % MOD;
            dp[i][1] = (dp[i - 1][0] + dp[i - 1][2]) % MOD;
            dp[i][2] = (dp[i - 1][0] + dp[i - 1][1]) % MOD;
        }

        System.out.println(dp[N - 1][0] % MOD);
    }
}

[풀이2]

2. 차례와 상관 없이 칸의 갯수에 따라서 채울 수 있는 방법을 생각해보는 경우

[코드2] - 시간초과

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


class Main {
    static int N;
    static long[] d;
    static long MOD = 1000000007;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        N = Integer.parseInt(br.readLine());

        d = new long[N + 1];
        System.out.println(dp(N));
    }

    static long dp(int x) {
        if (x == 0) return 1;
        if (x == 1) return 2;
        if (x == 2) return 7;
        if (d[x] != 0) return d[x];
        long result = 2 * dp(x - 1) + 3 * dp(x - 2);
        for (int i = 3; i <= x; i++) {
            result += (2 * dp(x - i)) % MOD;
        }
        return d[x] = result % MOD;
    }
}

결국 2*A
에서 A에 들어가는 식을 dp로 변환해서 중복 계산이 발생하지 않도록 해야한다.

[개선된 코드2]

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


class Main {
    static int N;
    static long[][] d;
    static int MOD = 1000000007;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        N = Integer.parseInt(br.readLine());

        d = new long[N + 1][2];
        System.out.println(dp(N));
    }

    static long dp(int x) {
        if(x == 1) return 2;

        d[0][0] = 0;
        d[1][0] = 2;
        d[2][0] = 7;
        d[2][1] = 1;

        for (int i = 3; i <= x; i++) {
            d[i][1] = (d[i - 1][1] + d[i - 3][0]) % MOD;
            d[i][0] = (2 * d[i - 1][0] + 3 * d[i - 2][0] + 2 * d[i][1]) % MOD;
        }
        return d[x][0];
    }
}