[DP] 3열 타일 채우기 + pro문제 타일 채우기
제일 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..
이기 때문에
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
|
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]);
}
}
|
cs |
이런 스탠스를 취하면 된다.
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
일단 타일에 빈공간 따른 경우의 수를 구해보자.
그럼 이것을 토대로 알고리즘을 만들어보자.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
|
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);
}
}
}
}
|
cs |