[SWEA] 4881 배열 최소 합 - python

https://swexpertacademy.com/main/learn/course/subjectDetail.do?courseId=AVuPDN86AAXw5UW6&subjectId=AWOVIc7KqfQDFAWg 

SW Expert Academy

N*N 배열에서 세로 안겹치고 뽑기

1~N까지 순열을 생성한 후, 그 순열에 해당하는 열을 배열에서 각각 뽑으면 된다 !

 

1. 순열 생성 함수 만들기

2. 생성된 순열과 배열 매칭해서 더하기

3. 더해진 값에서 최소값 찾기

방법으로 코드를 짯는데, 시간초과가 계속 났ㄷㅏ..

 

처음짠 코드 ( 시간초과 )

def f(i, k):
    total = 0
    if i == k:
        # arr랑 순열 매칭해서 뽑기
        for n in range(len(arr)):
            a = p[n]
            # 숫자 합쳐서 temp에 넣기
            total += arr[n][a]
        temp.append((total))
    else:
        # 자기 자신 i 부터 바꾸고 오른쪽이랑 바꾸기
        for j in range(i, k):
            p[i], p[j] = p[j], p[i]
            #  p[i]결정, p[i]와 관련된 작업 가능
            f(i + 1, k)
            p[i], p[j] = p[j], p[i]

T = int(input())
# 여러개의 테스트 케이스가 주어지므로, 각각을 처리합니다.
for test_case in range(1, T + 1):
    temp = []
    N = int(input())
    arr = list(list(map(int, input().split())) for _ in range(N))
    # 순열 만들기용 리스트
    p = [0]*N
    for i in range(N):
        p[i] = i
    ##################
    minV = 31
    f(0,N)
    # 제일 작은 값 찾기
    for i in temp:
        if i < minV:
            minV = i
    print(f'#{test_case} {minV}')

 

total을 매번 반복돌려서 구하기 X 

1. s + arr[i][[p[i]]를 재귀 돌려서 계속 갱신하기

2. s가 만약 minV보다 크면 나머지 돌아가지 않게 하기

 

시간줄이는 코드

def func(i, k, s):  # s : 앞에서 선택한 원소의 합
    global minV
    if i == k:
        # 원소의 합이 minV 보다 작으면, minV = s
        if minV > s:
            minV = s
        return
    # s가 minV보다 작으면 멈추기
    elif s >= minV:
        return
    else:
        for j in range(i, k):
            p[i], p[j] = p[j], p[i]
            func(i + 1, k, s + arr[i][p[i]])
            p[i], p[j] = p[j], p[i]
    return


T = int(input())
for test_case in range(1, T + 1):
    N = int(input())
    arr = [list(map(int, input().split())) for _ in range(N)]
    minV = 10 * N
    p = [i for i in range(N)]
    func(0, N, 0)
    print(f'#{test_case} {minV}')