https://mediawiki.zeropage.org/api.php?action=feedcontributions&feedformat=atom&user=141.98.9.23 2026-05-14T22:33:55Z User contributions MediaWiki 1.39.8 https://mediawiki.zeropage.org/index.php?title=1R/2016_10_07&diff=26088 2023-01-17T01:52:21Z

<p>141.98.9.23: 1</p> <hr /> <div>__TOC__<br /> <br /> = 오늘의 문제 =<br /> * [https://www.acmicpc.net/problem/1648|격자판 채우기]<br /> <br /> <br /> <br /> = 코드 =<br /> == 15이원준 ==<br /> #include&amp;lt;iostream&amp;gt;<br /> <br /> using namespace std;<br /> <br /> int dp[14*14][1&amp;lt;&amp;lt;15] = { 0, };<br /> int n, m;<br /> int search(int num, int bitma){<br /> if(dp[num][bitma]){<br /> if(dp[num][bitma] == -1){<br /> return 0;<br /> }<br /> return dp[num][bitma];<br /> }<br /> if(num == n * m - 1){<br /> if(bitma){<br /> return bitma;<br /> }<br /> dp[num][bitma] = -1;<br /> return 0;<br /> }<br /> if(bitma &amp;amp; 1){<br /> dp[num][bitma] = search(num + 1, bitma &amp;gt;&amp;gt; 1) % 9901;<br /> if(dp[num][bitma]){<br /> return dp[num][bitma];<br /> }<br /> dp[num][bitma] = -1;<br /> return 0;<br /> }<br /> if( num % m != m - 1 &amp;amp;&amp;amp; !((bitma &amp;gt;&amp;gt; 1) &amp;amp; 1)){<br /> dp[num][bitma] = search(num + 1, (bitma &amp;gt;&amp;gt; 1) + 1) % 9901;<br /> }<br /> if( num &amp;lt; (n-1) * m){<br /> dp[num][bitma] = (dp[num][bitma] + search(num + 1, (bitma &amp;gt;&amp;gt; 1) + (1&amp;lt;&amp;lt;(m-1)))) % 9901;<br /> }<br /> if(dp[num][bitma]){<br /> return dp[num][bitma];<br /> }<br /> dp[num][bitma] = -1;<br /> return 0;<br /> }<br /> <br /> <br /> int main(){<br /> cin&amp;gt;&amp;gt; n &amp;gt;&amp;gt; m;<br /> cout &amp;lt;&amp;lt; search(0, 0);<br /> <br /> }<br /> == 박인서 ==<br /> #include &amp;lt;iostream&amp;gt;<br /> #include &amp;lt;cstring&amp;gt;<br /> <br /> int d[14 * 14][1 &amp;lt;&amp;lt; 14];<br /> int n, m;<br /> <br /> int go(int t, int s) {<br /> if (t &amp;gt;= n*m) {<br /> if(t == n*m &amp;amp;&amp;amp; s == 0) return 1;<br /> return 0;<br /> }<br /> if (d[t][s] &amp;gt;= 0) return d[t][s] % 9901;<br /> <br /> int&amp;amp; res = d[t][s];<br /> if (s % 2 == 1) res=go(t + 1, s &amp;gt;&amp;gt; 1);<br /> else {<br /> res = go(t + 1, (s &amp;gt;&amp;gt; 1) | (1 &amp;lt;&amp;lt; m - 1));<br /> if (s % 4 == 0 &amp;amp;&amp;amp; t%m != (m - 1)) res+=go(t + 2, s &amp;gt;&amp;gt; 2);<br /> }<br /> <br /> return res % 9901;<br /> }<br /> <br /> int main() {<br /> std::cin &amp;gt;&amp;gt; n &amp;gt;&amp;gt; m;<br /> memset(d, -1, sizeof(d));<br /> std::cout &amp;lt;&amp;lt; go(0, 0);<br /> return 0;<br /> }<br /> <br /> == 곽정흠 ==<br /> <br /> = 아이디어 =<br /> == 15이원준 ==<br /> <br /> == 박인서 ==<br /> * 비트마스크를 이용한 DP<br /> <br /> == 곽정흠 ==<br /> </div>

141.98.9.23