[Python] 백준 1014 - 컨닝

https://www.acmicpc.net/problem/1014

풀이

맨 윗줄부터 아래로 내려가면서 dp할 것이다.

가로 길이가 최대 10밖에 안되므로 비트마스킹을 해서, 현재 행에 배치할 수 있는 학생 조합 마스크들을 구해놓자.

dp 정의는 dp[행번호][마스크] = (현재행번호까지 봤을 때 최대학생수)이다.

i번째 행을 살펴볼 때 가능한 마스크에 대해서 i-1번째 마스크들과 직접 비교해주며 가능한 경우 최댓값을 갱신해주면 된다.

 

import sys
input = sys.stdin.readline
C = int(input())
for t in range(C):
    N, M = map(int, input().split())
    graph = []
    for i in range(N):
        s = input().strip()
        graph.append(list(s))

    dp = [[0]*(1<<M) for _ in range(N)]
    av = [[False]*(1<<M) for _ in range(N)]
    for i in range(N):
        for mask in range(1<<M):
            for d in range(M):
                if mask & (1<<d):
                    if mask & (1<<(d+1)) or graph[i][M - 1 - d] == 'x' or (d >= 1 and mask & (1<<(d-1))):
                        break
            else: #이번 줄에서 가능한 마스크일때
                av[i][mask] = True

    for i in range(N):
        for mask in range(1<<M):
            if av[i][mask]:
                b = mask.bit_count()
                if i == 0:
                    dp[i][mask] = b
                else:
                    for prev in range(1<<M):
                        if av[i-1][prev]:
                            for d in range(M):
                                if mask & (1 << d):
                                    if prev & (1 << (d + 1)) or (d >= 1 and prev & (1<<(d-1))):
                                        break
                            else:
                                dp[i][mask] = max(dp[i][mask], dp[i-1][prev] + b)

    print(max(dp[-1]))