Difference between r1.2 and the current
@@ -4,13 +4,58 @@
* [https://www.acmicpc.net/problem/1648|격자판 채우기]
= 참가자 =
* 15이원준
* 박인서
= 코드 =
== 15이원준 ==
{{{
#include <iostream>
= 코드 =
== 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);
}
}}}
== 박인서 =={{{
#include <iostream>
2.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); }
2.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; }