[백준/python]2133번 타일 채우기 - bitmasking

매 열마다 3개의 타일이 있다.채워진 타일을 1, 채워지지 않은 타일을 0으로 표시한다.

ex)맨 위 타일 하나만 채워진 경우 100.

비트마스크는 알고리즘의 한 종류가 아닌 일종의 기법이라는 것을 해당 문제에서 알 수 있다. 점화식을 잘 표현하면 굳이 비트표현이 아닌 정수표현으로 풀어도 상관없다. 다만 0과 1의 직관적인 표현이 문제 풀이에 조금이나마 도움이 되었다.

N=int(input())
sol=0
if N%2==1:
    print(0)
else:
    dp=[ [1 for _ in range(8)] for _ in range(N+1) ]
    for i in range(2,N+1):
        if i%2==1: #홀수 일 때
            dp[i][0b110]=dp[i-1][0b001]+dp[i-1][0b111]
            dp[i][0b011]=dp[i-1][0b100]+dp[i-1][0b111]
            dp[i][0b000]=dp[i-1][0b111]
        else:
            dp[i][0b100]=dp[i-1][0b011]
            dp[i][0b001]=dp[i-1][0b110]
            dp[i][0b111]=dp[i-1][0b000]+dp[i-1][0b110]+dp[i-1][0b011]
    print(dp[N][0b111])

DP 표현

dp[x][y] = x번째 열에서 y 타일이 채워졌을 때 가능한 경우의 수

y를 비트마스킹 기법을 이용하여 채워진 타일을 표시한다. (백준 2098번 TSP문제에서 visited와 유사)

문제에서 주어진 N이 최대 8이므로 3자리 이진수로 모두 표현이 가능하다.

DP 점화식

1. 현재 열x가 홀수인 경우

1. dp[x][110] : x-1 열이 짝수이므로 다 채운 경우 dp[x-1][111]에 2x1 타일을 추가하는 경우, x-1열에서 001로 채워 dp[x-1][001]에 1x2 타일을 두 개 채우는 경우  
	
2. dp[x][011] : 위의 경우와 동일
	
3. dp[x][000] : 현재 열에서 아무것도 채우지 않은 경우. 이것은 x-1 열에서 모두 채운 경우와 동일하다. (=dp[x-1][111]

한 개만 채우는 경우는 불가능하다.

2. 현재 열x가 짝수인 경우

1. dp[x][100] : x-1 열은 홀수이므로 다 채우는 것이 불가능하다. dp[x-1][011]에 1X2 타일을 가장 위에 채우는 경우
	
2. dp[x][001] : 위의 경우와 동일
	
3. dp[x][111] : 모든 타일을 채우는 경우이다. x-1열에서 아무것도 채우지 않은 경우(dp[x-1][000]) 2x1 타일 3개로 채운다. x-1열에서  두 개를 채운 경우 2x1 타일과 1x2 타일을 사용하여 남은 공간을 채운다(dp[x-1][110], dp[x-1][011] 두 가지 경우 동일). 
	
마찬가지로 두 개를 채우는 경우는 불가능하다.