[삼성sw 2112] 보호필름(파이썬)

https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AV5V1SYKAaUDFAWu&categoryId=AV5V1SYKAaUDFAWu&categoryType=CODE&problemTitle=SW&orderBy=FIRST_REG_DATETIME&selectCodeLang=ALL&select-1=&pageSize=10&pageIndex=2 

SW Expert Academy

저를 포함한 많은 분들이

시간초과에서 애를 먹지 않았을까 생각해봅니다.

 

저도 이거 시도했을때

시간초과를 줄이지 못해서 통과가 안되더라고요.

그러다가 구글링으로 코드를 보고 겨우 공부했습니다.

https://chelseashin.tistory.com/69

[SWEA] 2112. 보호필름(Python) / DFS

제가 참고한 코드.

이 코드는 pick이라는 변수를 선언해서

'최대 약품을 몇개까지 넣는지'각각 살펴주는 방식이었습니다.

1~D번까지 살펴보면서

만약 값을 갱신한 바 있다면

그 값을 넣어주는 방식.

완전탐색으로 모든 경우를 다 탐색합니다.

T=int(input())

def test(room):
    for y in range(W):
        now=room[0][y]
        cnt=1
        for x in range(1,D):
            if now==room[x][y]:
                cnt+=1

            else:
                cnt=1
                now=room[x][y]
            if cnt>=K:
                break

        if cnt<K:
            return False

    return True

def dfs(depth,k,pick):
    global answer
    if depth>=answer:
        return

    if depth==pick:
        if test(room):
            answer=min(answer,depth)
        return

    for i in range(k,D):
        for d in range(2):
            select.append(i)
            room[i]=drugs[d]
            dfs(depth+1,i+1,pick)
            room[i]=raw[i]
            select.pop()

for t in range(1,T+1):
    D,W,K=map(int,input().split())
    room=[list(map(int,input().split())) for _ in range(D)]
    raw=[r[:] for r in room]
    drugs=[[0]*W,[1]*W]

    if test(room):
        answer=0

    else:
        answer=D
        select=[]
        #pick-->약품을 최대 얼마나 넣는지에 대한 갯수
        #최대 D까지 돌리면서 가능한지 여부를 체크한다.
        for pick in range(1,D+1):
            dfs(0,0,pick)
            if answer<D:
                break

    print("#%d %d"%(t,answer))

 

이 문제에서 어려웠던 부분은 가지치기.

완전탐색까지는 개념이 어느정도 잡히는데

'특정 부분은 탐색에서 배제한다'

라는 개념을 익혔습니다.