SWEA 2112 보호 필름(with Python)

• 문제에서 약품 투여 최소개수가 2라고 이해했다.

• 아니다 최소개수는 없다. 즉 1 ~ D 까지 막을 선택해서 약품 투여할 수 있다...ㅜ

import sys
sys.stdin = open(r'/Users/kangdaeyoung/Downloads/sample_input.txt', 'r')

T = int(input())

def check_test(selected):
    # 막 선택이 끝난 경우이므로 약품처리 궈궈
    # 각 층마다 무슨 약품을 쓸지 선택해야 함
    for case in range(1 << x):
        new_film = []
        for row in range(D):
            new_film.append(film[row][:])

        for idx in range(x):
            if case & (1 << idx):
                material = 0
            else:
                material = 1
            for col in range(W):
                new_film[selected[idx]][col] = material

        # 해당 방식으로 처리하면 테스트 통과하니?
        is_fine = True
        for col in range(W):
            max_length = 1
            check_length = 1
            first_value = new_film[0][col]
            for row in range(1, D):
                if first_value == new_film[row][col]:
                    check_length += 1
                else:
                    first_value = new_film[row][col]
                    if check_length > max_length:
                        max_length = check_length
                    check_length = 1
            # 마지막 부분까지 고려하기 위한 장치
            if check_length > max_length:
                max_length = check_length
            # 테스트 통과?
            if max_length < K:
                is_fine = False
                break
        if is_fine:
            return True


def comb(n, r, tmp):
    global find_strong_film, answer
    if not find_strong_film:
        if r == 0:
            # test 통과
            if check_test(selected):
                find_strong_film = True
                answer = x
        else:
            for i in range(tmp, n):
                selected[x-r] = i
                comb(n, r-1, i+1)
                selected[x-r] = 0


for tc in range(1, T+1):
    # 두께, 가로길이, 통과를 위한 최소 세기
    D, W, K = map(int, input().split())

    film = [list(map(int, input().split())) for _ in range(D)]

    find_strong_film = False
    answer = 0

    # [전략]
    # 약품을 최소로 써야 하니,
    # 먼저 막 2개를 골라서 테스트 궈궈
    # 안되면 막 3개, ..., D개까지
    # 단위 막 선택하고 나서 해당 막을 무슨 약품으로 처리할지도 정해야함

    # 약품을 투입안하고 통과하는지 체크
    is_fine = True
    for col in range(W):
        max_length = 1
        check_length = 1
        first_value = film[0][col]
        for row in range(1, D):
            if first_value == film[row][col]:
                check_length += 1
            else:
                first_value = film[row][col]
                if check_length > max_length:
                    max_length = check_length
                check_length = 1
        # 마지막 부분까지 고려하기 위한 장치
        if check_length > max_length:
            max_length = check_length
        # 테스트 통과?
        if max_length < K:
            is_fine = False
            break

    if is_fine:
        print(f'#{tc} {0}')
    else:
        # 막을 선택하고 모든 약품의 경우를 고려하는 함수
        for x in range(1, D+1):
            if not find_strong_film:
                selected = [0] * x
                comb(D, x, 0)

        print(f'#{tc} {answer}')