https://www.acmicpc.net/problem/14700
14700번: 넴모넴모 (Hard)
첫 번째 줄에 주어진 격자판에서 나올 수 있는, “넴모”들이 올라간 칸이 2 × 2 사각형을 이루지 않는 모든 배치의 가짓수를 1, 000, 000, 007로 나눈 나머지를 출력한다.
www.acmicpc.net
dp + 비트마스킹 문제로 격자판 채우기(문제 링크) 문제와 비슷한 방식으로 해결하였습니다.
(안 푸셨으면 풀어 보시는거 추천드립니다 ㅎㅎ)
dp[x][chk] : x번 칸에서 이전 M + 1개의 칸에 넴모가 채워져있는 상태가 chk인 경우의 수
이렇게 두고 해결하였습니다.
격자판 채우기 문제는 x번 칸부터 M개의 칸을 비트로 다루었고, 이 문제는 x번 칸 이전의 M+1개의 칸을 비트로 다루었습니다.
우선 맨 왼쪽 칸은 무조건 넴모를 놓을 수 있습니다.. 그 칸에 놓음으로 2 * 2 사각형을 만들 수 없기 때문입니다.
이부분도 생각해주셔야합니다. (x % M == 0 인 곳)
만약 2 * 3 격자판에 칸이 이렇게 채워져있고, x번 칸 차례라고 한다면,
M + 1개의 비트는 x - 1부터 해서 역순으로 1101이라고 생각하시면 됩니다.
그럼 x번 칸에서 봐야할 비트는 (1 << 0) , (1 << 1), (1 << M) 이렇게 3개입니다.
위의 그림에서는 (1 << 1) 비트가 0이므로 x에는 넴모를 올려놓은 것, 올려놓지 않은 것 모두 확인할 수 있습니다.
만약 이 그림이라면 3개의 비트 모두 1이므로 x에는 넴모를 올려놓지 않은 것만 확인하시면 됩니다.
그리고.. 이 문제가 메모리가 빠듯해서 그런지 1 << 19로 잡아도 메모리 초과가 발생하였습니다.
입력이 N * M <= 300으로 들어오기때문에 10 * 30 이런것도 들어올 수 있다는 것인데
비트는 M + 1개를 다루기 때문에 메모리 공간을 잡는데 어려움이 있었습니다.
17 * 17 = 289이고 18 * 18 = 324이므로 아무리 커도 N과 M 중 작은쪽은 17보다 클 수 없다는 생각을 하였고,
둘 중 작은쪽을 M으로 가게 하였습니다.
시간 제한이 2초인데 1.6초로 겨우 AC를 받았습니다..
|
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
|
#include <iostream>
#include <cstring>
#define MOD 1000000007
using namespace std;
int dp[301][1 << 18];
int N, M;
int func(int x, int chk) {
if (x == N * M) return 1;
int &ret = dp[x][chk];
if (ret != -1) return ret;
ret = 0;
ret = func(x + 1, chk >> 1);
if (!(x % M) || !(chk & (1 << 0)) || !(chk & (1 << 1)) || !(chk & (1 << M))) {
ret = (ret + func(x + 1, (chk >> 1) | (1 << M))) % MOD;
}
return ret;
}
void input() {
cin >> N >> M;
if (N < M) swap(N, M);
memset(dp, -1, sizeof(dp));
}
int main() {
cin.tie(NULL); cout.tie(NULL);
ios::sync_with_stdio(false);
input();
cout << func(0, 0) << '\n';
return 0;
}
|
cs |
'algorithm > dp' 카테고리의 다른 글
| boj 17090 미로 탈출하기 (0) | 2021.06.27 |
|---|---|
| boj 1648 격자판 채우기 (0) | 2021.06.22 |
| boj 1311 할 일 정하기 1 (0) | 2021.06.21 |
| boj 1577 도로의 개수 (0) | 2021.06.20 |
| boj 4781 사탕 가게 (0) | 2021.06.19 |