[파이썬] 4881. 배열 최소 합

swexpertacademy.com/main/learn/course/lectureProblemViewer.do

SW Expert Academy

 

※ SW Expert 아카데미의 문제를 무단 복제하는 것을 금지합니다.


NxN 배열에 숫자가 들어있다. 한 줄에서 하나씩 N개의 숫자를 골라 합이 최소가 되도록 하려고 한다. 단, 세로로 같은 줄에서 두 개 이상의 숫자를 고를 수 없다.

조건에 맞게 숫자를 골랐을 때의 최소 합을 출력하는 프로그램을 만드시오.

예를 들어 다음과 같이 배열이 주어진다.
 

2	1	2
5	8	5
7	2	2

이경우 1, 5, 2를 고르면 합이 8로 최소가 된다.

 

[입력]
 

첫 줄에 테스트 케이스 개수 T가 주어진다.  1≤T≤50
 

다음 줄부터 테스트 케이스의 첫 줄에 숫자 N이 주어지고, 이후 N개씩 N줄에 걸쳐 10보다 작은 자연수가 주어진다. 3≤N≤10

 

[출력]
 

각 줄마다 "#T" (T는 테스트 케이스 번호)를 출력한 뒤, 합계를 출력한다.

입력	출력
3 3 2 1 2 5 8 5 7 2 2 3 9 4 7 8 6 5 5 3 7 5 5 2 1 1 9 3 3 8 3 1 9 2 8 8 6 1 5 7 8 3 5 5 4 6 8	#1 8 #2 14 #3 9

 

🎀 다른사람 풀이

 

def MyCalc(y) :
    global sub_result, result
    
    if result < sub_result :
        return
    
    if y == N :		# lst의 행을 다 돌면
        if sub_result < result :
            result = sub_result
        return
    
    for x in range(N) :
        if not visited[x] :
            visited[x] = True
            sub_result += lst[y][x]
            MyCalc(y+1)
            visited[x]=False
            sub_result -= lst[y][x]
            
TC = int(input())
# 여러개의 테스트 케이스가 주어지므로, 각각을 처리합니다.
for tc in range(1, TC + 1):
    N=int(input())
    lst=[list(map(int, input().split())) for _ in range(N)]
    visited=[0]*N
    sub_result, result=0, 987654321
    MyCalc(0)
    
    print(f"#{tc} {result}")

 

N번 입력받은 값들을 리스트로 lst에 저장한다.

N의 크기만큼 리스트 visited를 초기화한다.

y랑 N이 같고(lst의 행을 다 돌면) sub_result가 result보다 작으면 result에 sub_result를 할당한다. 더 작은 값으로 결과값인 result를 갱신.

sub_result는 시작한 행의 합을 구하는 변수.

N번 반복문을 돌린다.

visited[x]의 값이 False라면 visited[x]를 True로 만든다.

sub_result에 lst[y][x]의 값을 더해간다. MyClac함수를 재귀호출한다. 그 다음 행의 값과 더할려고.

return한 뒤 visited[x]를 False로 만든다. sub_result에서 lst[y][x]를 뺀다. sub_result 초기화.

 

x=2

visited=t,t,f

sub_result=10

 

x=1

visited=t,f,f

sub_result=2

 

x=2

visited=t,f,t

sub_result=7

 

y=2

visited=t,t,t

sub_result=9

 

y=3

y==n이고 sub_result<result이므로 result=9로 return

visited=t,f,t

sub_result=7

 

x=2

visited=t,f,f

sub_result=2

 

x=0

visited=f,f,f

sub_result=0

 

x가 1부터 다시 시작

 

def count(idx, visited, SUM) :
    global MIN
    if idx >= N :
        if SUM < MIN :
            MIN = SUM
        return

    if SUM > MIN :
        return
    for k in range(0, N) :
        if visited[k] == 0 :    # k번째 값에 접근한 적이 없다면
            SUM += maze[idx][k]
            visited[k] = 1
            count(idx+1, visited, SUM)
            visited[k]=0    # 원상복구
            SUM -= maze[idx][k]

T=int(input())
for TC in range(1, T+1) :
    N=int(input())
    maze=list()
    for i in range(N) :
        arr=list(map(int, input().split()))
        maze.append(arr)

    visited={}
    for i in range(0, N) :
        visited[i]=0
    SUM=0
    MIN=99999

    count(0, visited, SUM)

    print("#%d %d" %(TC, MIN))

 

visited를 딕셔너리로 만들었다. visited의 key값은 인덱스고 초기값은 0이다.

count함수를 호출한다. idx가 N보다 크거나 같고(같다라고만 하는게 더 정확함) SUM < MIN이면 MIN에 SUM을 할당.

visited[k]가 0이면 SUM에 maze[idx][k]를 더한다. visited[k]를 1로 만든다.

count함수를 재귀호출한다.

visited[k]를 0으로 만들고 SUM에서 maze[idx][k]를 뺀다. 

알고리즘이 첫번째 코드와 같음.