[BOJ] 14852. 타일 채우기 3
[작성일]
- 2022-03-24
[분류]
- dp
[문제링크]
[요구사항]
2×N 크기의 벽을 2×1, 1×2, 1×1 크기의 타일로 채우는 경우의 수를 구해보자.
경우의 수를 1,000,000,007로 나눈 나머지를 출력하자.
굉장히 어려운 문제였다고 생각한다.
- 두 가지 방법을 이용해서 풀어보았다.
[풀이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] - 시간초과
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];
}
}
Author And Source
이 문제에 관하여([BOJ] 14852. 타일 채우기 3), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다 https://velog.io/@hyodonglee/BOJ-14852.-타일-채우기-3저자 귀속: 원작자 정보가 원작자 URL에 포함되어 있으며 저작권은 원작자 소유입니다.
우수한 개발자 콘텐츠 발견에 전념 (Collection and Share based on the CC Protocol.)