알고리즘 공부방

문제 https://www.acmicpc.net/problem/1648 N*M 크기의 격자판을 2*1 모양의 타일로 채우는 경우의 수를 출력하는 문제이다. 풀이 일단 당연히 비트마스크 dp 문제이다. 더욱 자세한 풀이는 https://www.slideshare.net/Baekjoon/baekjoon-online-judge-1648 을 참고하자. 이와 같이 각 칸에 번호를 붙이자. solve(pos, mask) = pos 번째 위치 전까지의 번호는 모두 채워져 있고, 비트마스크가 mask 일때 경우의 수를 의미한다. 비트마스크의 표현 범위는 만약 pos 가 15라면 15~20을 표현한다. 21번부터는 표현할 필요가 없음을 알 수 있다. 왜냐하면 21번을 포함하는 타일이 1~14중 하나를 동시에 포함할 수가..