문제

SWEA-2112 : [모의 SW 역량테스트] 보호 필름

풀이

어느 Layer에 약품을 넣을 것인지 결정하면 되기 때문에 DFS로 풀 수도 있다. 나는 약품을 넣을 열의 조합과 각 열에 넣을 약품의 조합을 미리 만들고 for문을 돌리는 방식으로 설계했다.

그래서 그런지 초과시간이 계속 나와서.. 시간 잡아먹는 부분을 고치느라 애먹었다. 나중을 위해 아래 부분을 적어둔다.

copy.deepcopy()는 순수한 python 모듈이다. 거의 0.1초 이상을 잡아먹으니 [ layer[:] for layer in film ] 구문을 기억하자.
입력이 str이므로 str로 처리해야 하는 부분이 있다면 습관적으로 입력을 받을 때 map(int, ...)부분을 사용하지 말자.
tuple이 list보다 빠르다.
itertools객체를 이용해 iterate할 경우, iterable 객체로 바꾸어주지 않아도 된다.

import itertools

def inspect(film):
    for L in film:
        layer = ''.join(L)
        if '1'*K not in layer and '0'*K not in layer:
            return 0
    return 1


def inject(film):
    for i in range(1, D+1):
        # 열 선택
        tries = itertools.combinations(tuple(range(D)), i)
        # 열에 넣을 약품 선택
        combs = tuple(itertools.product(['0', '1'], repeat=i))

        for tri in tries:
            filmtemp = [ layer[:] for layer in film ]
            for comb in combs:
                for l, row in enumerate(tri):
                    for m in range(W):
                        filmtemp[m][row] = comb[l]
                if inspect(filmtemp):
                    return i
    return -1


T = int(input())
# for test_case in [1]:
for test_case in range(1, T + 1):
    maxi = 0
    D, W, K = map(int, input().split())

    arr = [[0]*D for _ in range(W)]
    for i in range(D):
        eles = input().split()
        for j in range(W):
            arr[j][i] = eles[j]
    # arr = list(map(list, zip(*arr)))

    if inspect(arr):
        maxi = 0
    else:
        maxi = inject(arr)

    print("#%d %d" % (test_case, maxi))