SWEA #4881 배열 최소 합

1. 완전 탐색의 기본

기억하자 for 문을 돌려야 될 수도? → 언제나 for 문에 대한 열린 생각!!

2. 기본적인 순열 & back-tracking 문제

• 완전 탐색을 하면 ⇒ 시간초과 에러가 발생하였다!

• back-tracking을 통해서 중간까지의 합이 현재의 최솟값보다 크면(앞으로는 더해야 하므로 가망이 없기 때문에) 리턴하는 방식으로 가지치기를 진행해주었다.

  → 이를 위해서 함수에 tmp 라는 인자를 가지고 다닌다.

이 테크닉을 이후에 유용하게 잘 써먹고 있다!

# 각 줄에 대해서 하나씩 선택하는 함수를 만든다
def select(i, k, tmp):
    global min_V
    if tmp > min_V:
        return
    
    if i == k:
        min_V = min(min_V, tmp)
        return
    else:
        for j in range(N):
            if not visited[j]:
                visited[j] = 1
                select(i+1, k, tmp+board[i][j])
                visited[j] = 0

T = int(input())
for tc in range(1, T+1):
    N = int(input())
    board = [list(map(int, input().split())) for _ in range(N)]
    min_V = 100
    visited = [0] * N
    select(0, N, 0)

    print(f"#{tc} {min_V}")

Uploaded by N2T