質問元:[SWEA]4881最小アレイ数
learn->course->プログラミングブローカ->スタック2->最小配列

質問する

nxn配列には数値が含まれています.1行から1つずつN個の数字を選び、最小にしたい.ただし、同じ行から縦に2つ以上の数字を選択することはできません.
条件に従って数字を選択したときの最小和を出力するプログラムを作成します.

入力

第1行は、試験用例数Tを与える.1≤T≤50
次の行から、試験例の最初の行には数Nが与えられ、その後、N行ごとに10未満の自然数が与えられる.3≤N≤10

しゅつりょく

各行に「#T」(Tはテストケース番号)を出力し、合計を出力します.

コード#コード#

# 최소합을 찾는 함수
def find_sum(num):
    # 최종 결과를 저장할 변수와, 숫자들의 합을 임시로 저장할 변수
    global min_sum, sum_num

    # 찾은 최소합보다 임시로 저장한 합이 더 클 경우엔 더 이상 최소값이 아니기 때문에 return
    if min_sum < sum_num:
        return

    # 마지막줄까지 탐색을 끝낸 경우
    if num == N:
        if sum_num < min_sum:   # 두 변수에 저장된 값 중 최소값을 최종 결과를 저장할 변수에 넣어줌
            min_sum = sum_num

    # 세로줄을 돌면서 탐색
    for i in range(N):
        if not visited[i]:      # 방문하지 않았을 경우
            visited[i] = 1      # 방문했다고 표시
            sum_num += num_list[num][i]     # 현재 인덱스 위치의 값울 임시 합 변수에 저장함
            find_sum(num + 1)       # 다음 줄로 넘어가서 확인
            visited[i] = 0          # 확인이 끝나고 방문 표시와 앞서 더해줌 값을 다시 빼줌
            sum_num -= num_list[num][i]


T = int(input())
for tc in range(1, T + 1):
    N = int(input())
    num_list = [list(map(int, input().split())) for _ in range(N)]
    visited = [0] * N       # 방문 표시를 할 리스트
    sum_num = 0             # 임시 합을 저장할 변수
    min_sum = 10 * N        # 최솟값을 저장할 변수
    find_sum(0)             # 함수 호출

    print(f'#{tc} {min_sum}')

解答方法

dfsを用いて解いたが,問題条件は縦線に1つ以上の数を選択できないことであるため,縦線を基準に解いた.探索を継続する過程で,変数に総和を格納することにより,変数に格納された総和が最終出力結果値の変数よりも小さい場合,値を更新する方式で解く.