[SWEA] 2112 : 보호필름 - Python

Chooooo·2024년 6월 14일
0

알고리즘/백준

목록 보기
189/204

문제

보호필름. 각 셀은 특성 A 또는 특성 B
합격기준 K, 충격 세로 방향으로 주어짐.
각 열마다 동일한 특성의 셀들이 K개 이상 연속적으로 있으면 해당 열은 통과
성능 검사 통과하기 위해 약품 사용.
최소 약품 투입 횟수 구하기

내 코드

import sys
sys.stdin = open("input.txt", "rt")

# 보호필름. 각 셀은 특성 A 또는 특성 B
# 합격기준 K, 충격 세로 방향으로 주어짐.
# 각 열마다 동일한 특성의 셀들이 K개 이상 연속적으로 있으면 해당 열은 통과
# 성능 검사 통과하기 위해 약품 사용.
# 최소 약품 투입 횟수 구하기

def 확인(g):
    for j in range(m):
        flag = False # 해당 열 가능한지 판단.
        for i in range(n):
            cnt = 0
            end = i
            now = g[i][j]
            while end < n and now == g[end][j]:
                cnt += 1
                end += 1
                if cnt >= k and not flag:
                    flag = True
                    break
            if flag:
                break
        if not flag:
            return False
    return True


def 성능검사(L, now, g):
    global res
    if now >= res:
        return
    if 확인(g):
        res = min(res, now)
    else: # 조합. 약품 사용.
        for i in range(L, n):
            for j in range(2):
                copy_g = [arr[:] for arr in g]
                for k in range(m):
                    copy_g[i][k] = j
                성능검사(i+1, now+1, copy_g)


T = int(input())
for t in range(1,T+1):
    n,m,k = map(int, input().split())
    g = [list(map(int, input().split())) for _ in range(n)]
    # 특성은 0 또는 1
    res = int(1e9)
    성능검사(0,0,g)
    print(f"#{t} {res}")

코멘트

DFS시에 가지치기 꼭 생각하자. 시간초과를 염두해야함!!! + 2차원 리스트 슬라이싱을 통한 복사.

  • 조합 코드 복기
profile
back-end, 지속 성장 가능한 개발자를 향하여

0개의 댓글