✅[모의 SW 역량테스트] 보호 필름

문제 출처 : https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AV5V1SYKAaUDFAWu&categoryId=AV5V1SYKAaUDFAWu&categoryType=CODE&problemTitle=%EB%AA%A8%EC%9D%98&orderBy=FIRST_REG_DATETIME&selectCodeLang=ALL&select-1=&pageSize=20&pageIndex=1 

SW Expert Academy

 

#1. 설계 및 풀이

문제 : 성능 검사를 통과할 수 있는 최소 약품 투입 횟수?
입력 : 두께 D[3, 13]/ 가로 크기 w[1, 20]/ 합격기준 k[1, D]/ 특성 A=0, 특성 B=1
조건 :
1) 특성은 A, B 두가지만 존재
2) 세로 방향에대해 동일한 특성의 셀들이 k개 이상 연속적인 경우 성능검사 통과
3) 막별로 약품 투입 가능 -> 막의 모든 셀들은 하나의 특성으로 변경

아이디어 : 완탐

 

1. 길이가 K보다 크지않은 조합을 만들기 (** 약품 종류까지 고려)

2. 조합을 적용한 배열이 통과하면 answer 갱신 후 리턴

3. 통과하지않으면 1부터 다시 반복

 

import copy

def is_possible(arr) :
    start = 0
    total = 0
    for end in range(len(arr)) :
        total += arr[end]
        if end-start == K-1 :
            if total == 0 or total == K :
                return True
            total -= arr[start]
            start += 1
    return False

def check_pass(board) :
    for j in range(W):
        arr = []
        for i in range(D):
            arr.append(board[i][j])
        if not is_possible(arr):
            return False
    return True

def dfs(start, visited) :
    global answer
    if len(visited) > K :
        return

    # copy.deepcopy(board) #copy대신 밑의 코드를 사용했더니 통과함
    temp = [b[:] for b in board]
    for i, type in visited :
        for j in range(W) :
            temp[i][j] = type

    if check_pass(temp) :
        if len(visited) < answer :
            answer = len(visited)
        return

    for i in range(start, D) :
        for type in range(2) :
            dfs(i+1, visited+[[i, type]])

TC = int(input())
for tc in range(1, TC+1) :
    D, W, K = map(int, input().split())
    answer = K
    board = [list(map(int, input().split())) for _ in range(D)]

    dfs(0, [])

    print("#{} {}".format(tc, answer))

 

 

#2. 배운 점

 

- 구현은 했는데 시간초과로 시간을 많이 잡아먹은 문제

--> copy의 deepcopy 모듈은 느리기때문에 슬라이싱을 이용하는 것이 훨씬 빠르다.

 

arr1 = [1, 2, 3, 4]

arr2 = [[1, 2], [3, 4]]

1차원 배열의 슬라이싱 : arr = arr1[:]

2차원 배열의 슬라이싱 : arr = [a[:] for a in arr2]

 

하지만 위의 코드는 시간복잡도가 O(2^13 * 13!)정도 나오므로 좋은 코드는 아닌 것 같다.

실제로 다음과 같은 예시를 넣으면 60초가 나온다.

13 20 12
1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0
0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1
1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0
0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1
1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0
0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1
1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0
0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1
1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0
0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1
1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0
0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1
1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0

 

--> 백트래킹을 통해 개선해야한다.

 

 

+) 조금 더 개선된 풀이

: 모든 행에 대해서 3가지 경우 (약품X, 약품1, 약품2)에 대해 재귀호출

--> answer이 작게 갱신되면, answer보다 같거나 많은 행에 대해 약품처리할 필요가 없으니까 백트래킹

 

마찬가지로 이 코드도 위의 케이스를 테스트하면 24초정도가 나온다.

오래걸리지만 성능은 확실히 빨라졌다.

 

import time

def is_possible(arr) :
    start = 0
    total = 0
    for end in range(len(arr)) :
        total += arr[end]
        if end-start == K-1 :
            if total == 0 or total == K :
                return True
            total -= arr[start]
            start += 1
    return False

def check_pass(board) :
    for j in range(W):
        arr = []
        for i in range(D):
            arr.append(board[i][j])
        if not is_possible(arr):
            return False
    return True

def dfs(start, cnt) :
    global answer, board
    if cnt >= answer : ######## 백트래킹
        return

    if start == D :
        if check_pass(board):
            answer = cnt
        return

    dfs(start+1, cnt) # 약품 X
    for j in range(W) : # 약품1
        board[start][j] = 0
    dfs(start+1, cnt+1)
    for j in range(W) : # 약품 2
        board[start][j] = 1
    dfs(start+1, cnt+1)

    # 원상복구
    # board[start] = temp[start] 주의!!!!!! 얕은복사임
    for j in range(W) :
        board[start][j] = temp[start][j]


TC = int(input())
for tc in range(1, TC+1) :
    stime = time.time()
    D, W, K = map(int, input().split())
    answer = K
    board = [list(map(int, input().split())) for _ in range(D)]
    temp = [b[:] for b in board]
    dfs(0, 0)
    print("#{} {}".format(tc, answer))
    # print(time.time() - stime)

 

위의 성능이 더 빠르지만, 첫번째 코드를 백트래킹을 통해 좀 더 개선한 코드

# import time

def is_possible(arr) :
    start = 0
    total = 0
    for end in range(len(arr)) :
        total += arr[end]
        if end-start == K-1 :
            if total == 0 or total == K :
                return True
            total -= arr[start]
            start += 1
    return False

def check_pass(board) :
    for j in range(W):
        arr = []
        for i in range(D):
            arr.append(board[i][j])
        if not is_possible(arr):
            return False
    return True

def dfs(start, visited) :
    global answer
    if len(visited) >= answer : ## 백트래킹 적용
        return

    # copy.deepcopy(board) #copy대신 밑의 코드를 사용했더니 통과함
    temp = [b[:] for b in board]
    for i, type in visited :
        for j in range(W) :
            temp[i][j] = type

    if check_pass(temp) :
        if len(visited) < answer :
            answer = len(visited)
        return

    for i in range(start, D) :
        for type in range(2) :
            dfs(i+1, visited+[[i, type]])

TC = int(input())
for tc in range(1, TC+1) :
    # stime = time.time()
    D, W, K = map(int, input().split())
    answer = K
    board = [list(map(int, input().split())) for _ in range(D)]
    dfs(0, [])
    print("#{} {}".format(tc, answer))
    # print(time.time()-stime)