Latest revision as of 14:46, 26 March 2026

오늘의 문제

채우기

코드

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>
#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;
}

1R/2016 10 07: Difference between revisions

Latest revision as of 14:46, 26 March 2026

오늘의 문제

코드

15이원준

박인서

곽정흠

아이디어

15이원준

박인서

곽정흠

@@ Line 5: / Line 5: @@
-= 참가자 =
-* 15이원준
-* 박인서
 = 코드 =
 == 15이원준 ==
+ #include&lt;iostream&gt;
+ using namespace std;
+ int dp&#91;14*14&#93;&#91;1&lt;&lt;15&#93; = { 0, };
+ int n, m;
+ int search(int num, int bitma){
+   if(dp&#91;num&#93;&#91;bitma&#93;){
+     if(dp&#91;num&#93;&#91;bitma&#93; == -1){
+       return 0;
+     }
+     return dp&#91;num&#93;&#91;bitma&#93;;
+   }
+   if(num == n * m - 1){
+     if(bitma){
+       return bitma;
+     }
+     dp&#91;num&#93;&#91;bitma&#93; = -1;
+     return 0;
+   }
+   if(bitma &amp; 1){
+     dp&#91;num&#93;&#91;bitma&#93; = search(num + 1, bitma &gt;&gt; 1) % 9901;
+     if(dp&#91;num&#93;&#91;bitma&#93;){
+       return dp&#91;num&#93;&#91;bitma&#93;;
+     }
+     dp&#91;num&#93;&#91;bitma&#93; = -1;
+     return 0;
+   }
+   if( num % m != m - 1 &amp;&amp; !((bitma &gt;&gt; 1) &amp; 1)){
+     dp&#91;num&#93;&#91;bitma&#93; = search(num + 1, (bitma &gt;&gt; 1) + 1)  % 9901;
+   }
+   if( num &lt; (n-1) * m){
+     dp&#91;num&#93;&#91;bitma&#93; = (dp&#91;num&#93;&#91;bitma&#93; + search(num + 1, (bitma &gt;&gt; 1) + (1&lt;&lt;(m-1))))  % 9901;
+   }
+   if(dp&#91;num&#93;&#91;bitma&#93;){
+     return dp&#91;num&#93;&#91;bitma&#93;;
+   }
+   dp&#91;num&#93;&#91;bitma&#93; = -1;
+   return 0;
+ }
+ int main(){
+   cin&gt;&gt; n &gt;&gt; m;
+   cout &lt;&lt; search(0, 0);
+ }
 == 박인서 ==
+ #include &lt;iostream&gt;
+ #include &lt;cstring&gt;
+ int d&#91;14 * 14&#93;&#91;1 &lt;&lt; 14&#93;;
+ int n, m;
+ int go(int t, int s) {
+     if (t &gt;= n*m) {
+         if(t == n*m &amp;&amp; s == 0) return 1;
+         return 0;
+     }
+     if (d&#91;t&#93;&#91;s&#93; &gt;= 0) return d&#91;t&#93;&#91;s&#93; % 9901;
+     int&amp; res = d&#91;t&#93;&#91;s&#93;;
+     if (s % 2 == 1) res=go(t + 1, s &gt;&gt; 1);
+     else {
+         res = go(t + 1, (s &gt;&gt; 1) | (1 &lt;&lt; m - 1));
+         if (s % 4 == 0 &amp;&amp; t%m != (m - 1)) res+=go(t + 2, s &gt;&gt; 2);
+     }
+     return res % 9901;
+ }
+ int main() {
+     std::cin &gt;&gt; n &gt;&gt; m;
+     memset(d, -1, sizeof(d));
+     std::cout &lt;&lt; go(0, 0);
+     return 0;
+ }
 == 곽정흠 ==
@@ Line 20: / Line 92: @@
 == 박인서 ==
+* 비트마스크를 이용한 DP
 == 곽정흠 ==