SWE(4881)_배열의_최소_합

작성일 | In

SWE 4881 배열의 최소 합

참고 문제

[참고교재_파이썬알고리즘]https://m.blog.naver.com/ydot/221387998142

참고 문제를 먼저 풀고 나서 그 다음 문제를 풀겠다.

참고문제 : 주어진 3x3 행렬에서 각 행과 열이 중복되지 않도록 숫자를 선택하고, 선택한 숫자들의 최소합을 구하는 알고리즘을 작성해보자.


INT_MAX = 10000
m = [[9, 4, 7], [8, 6, 5], [7, 2, 2]]

col_check = [False]*3
min_sol = INT_MAX


def func(row, score):
    global min_sol

    if row == 3:
        if score < min_sol:
            min_sol = score
        return min_sol
    for i in range(3):
        if col_check[i] == False:
            col_check[i] = True
            func(row+1, score+m[row][i])
            col_check[i] = False
    return min_sol


if __name__ == "__main__":
    print(func(0, 0))

아.. 이걸로 문제를 왜 못 풀겠지..

제한시간 초과

m = []
col_check = []
min_sol = 10000
N = 0


def func(row, score):
    global min_sol
    # 기본적으로 전역변수는 어디에서나 읽을 수 있지만, 함수 안에서 전역변수에 새로운 값을 '대입'하는 것은 불가능하다.
    # global 키워드를 사용하면 전역변수에 새로운 값을 대입할 수 있다.
    if row == N:
        if score < min_sol:
            min_sol = score
        return min_sol
    for i in range(N):
        if col_check[i] == False:
            col_check[i] = True
            func(row+1, score+m[row][i])
            col_check[i] = False
    return min_sol


if __name__ == "__main__":
    TC = int(input())
    for tc in range(1, TC+1):
        min_sol = 10000
        N = int(input())
        arr = [list(map(int, input().split())) for i in range(N)]
        m = arr
        col_check = [False]*N
        print("#%s %s" % (tc, func(0, 0)))

코드 참고

나는 기존에 checked라는 배열을 둠으로써, 그 안에 False,False,False로 디폴트 값을 주고 (행 수만큼) 반복문을 돌 때, 중복이 되는 부분들에 대해서 제한을 걸어둠으로써, 예를 들어 3x3 배열이라면 9번의 포문이 돌겠지만 각각 사전에 checked라는 배열의 조건을 검사하여 6번으로 단축시킬 수 있었다.

이것 외에도 시간을 어떻게 단축 시킬 수 있을까?

def MyCalc(row):
    global sub_result, result
    # sub_result란, 시작한 행의 합을 구하는 변수다.
    # sub result가 result보다 크면 함수 종료
    # print("row : %s, result : %s sub_result :  %s" % (row, result, sub_result))
    if result < sub_result:
        return
    # 혹시나, 2개만 더했는데도 기존의 result 값 보다 클 수 있다. 최소값을 구하는 문제니까 그럼 더 구할 필요가 없어진다.

    # 마지막 행에 도착했을 때, result 갱신 및 종료
    if row == N:
        if sub_result < result:
            result = sub_result
        return

    for i in range(N):
        if not visited[i]:  # x가 false라면
            visited[i] = True  # visited 배열 방문했다는 의미로, True로 바꿔주고
            sub_result += arr[row][i]  # sub_result를 갱신
            # print("row: % s, i: % s, visited: % s, sub_result: % s, result: % s "
            #   % (row, i, visited, sub_result, result))
            MyCalc(row+1)
            visited[i] = False
            sub_result -= arr[row][i]  # 더했던 값 빼주서 sub_result 초기화


T = int(input())
for tc in range(1, T+1):
    N = int(input())
    arr = [list(map(int, input().split())) for _ in range(N)]
    visited = [0] * N
    sub_result, result = 0, 99999999
    MyCalc(0)
    print(f'#{tc} {result}')

– 참고자료 [global변수]https://korbillgates.tistory.com/98 [전역변수개념]https://edu.goorm.io/learn/lecture/3493/%EB%B0%94%EB%A1%9C-%EC%8B%A4%ED%96%89%ED%95%B4%EB%B3%B4%EB%A9%B4%EC%84%9C-%EB%B0%B0%EC%9A%B0%EB%8A%94-%ED%8C%8C%EC%9D%B4%EC%8D%AC3/lesson/412512/%EC%A0%84%EC%97%AD%EB%B3%80%EC%88%98%EC%99%80-%EC%A7%80%EC%97%AD%EB%B3%80%EC%88%98

0%