• 15이원준
• 박인서

3. 코드 ¶

3.1. 15이원준 ¶

```#include<iostream>

using namespace std;

int dp[14*14][1<<15] = { 0, };
int n, m;
int search(int num, int bitma){
if(dp[num][bitma]){
if(dp[num][bitma] == -1){
return 0;
}
return dp[num][bitma];
}
if(num == n * m - 1){
if(bitma){
return bitma;
}
dp[num][bitma] = -1;
return 0;
}
if(bitma & 1){
dp[num][bitma] = search(num + 1, bitma >> 1) % 9901;
if(dp[num][bitma]){
return dp[num][bitma];
}
dp[num][bitma] = -1;
return 0;
}
if( num % m != m - 1 && !((bitma >> 1) & 1)){
dp[num][bitma] = search(num + 1, (bitma >> 1) + 1)  % 9901;
}
if( num < (n-1) * m){
dp[num][bitma] = (dp[num][bitma] + search(num + 1, (bitma >> 1) + (1<<(m-1))))  % 9901;
}
if(dp[num][bitma]){
return dp[num][bitma];
}
dp[num][bitma] = -1;
return 0;
}

int main(){
cin>> n >> m;
cout << search(0, 0);

}
```

3.2. 박인서 ¶

```#include <iostream>
#include <cstring>

int d[14 * 14][1 << 14];
int n, m;

int go(int t, int s) {
if (t >= n*m) {
if(t == n*m && s == 0) return 1;
return 0;
}
if (d[t][s] >= 0) return d[t][s] % 9901;

int& res = d[t][s];
if (s % 2 == 1) res=go(t + 1, s >> 1);
else {
res = go(t + 1, (s >> 1) | (1 << m - 1));
if (s % 4 == 0 && t%m != (m - 1)) res+=go(t + 2, s >> 2);
}

return res % 9901;
}

int main() {
std::cin >> n >> m;
memset(d, -1, sizeof(d));
std::cout << go(0, 0);
return 0;
}
```

4. 아이디어 ¶

4.2. 박인서 ¶

• 비트마스크를 이용한 DP