[SW Expert Academy] 5188. 최소합

5188. 최소합

---

문제)

그림처럼 NxN 칸에 숫자가 적힌 판이 주어지고, 각 칸에서는 오른쪽이나 아래로만 이동할 수 있다.

맨 왼쪽 위에서 오른쪽 아래까지 이동할 때, 지나는 칸에 써진 숫자의 합계가 최소가 되도록 움직였다면 이때의 합계가 얼마인지 출력하는 프로그램을 만드시오.

 

 

그림의 경우 1, 2, 3, 4, 5순으로 움직이고 최소합계는 15가 된다. 가능한 모든 경로에 대해 합을 계산한 다음 최소값을 찾아도 된다.

 

 

[입력]

첫 줄에 테스트케이스의 수 T가 주어진다. 1<=T<=50

다음 줄부터 테스트 케이스의 별로 첫 줄에 가로 세로 칸 수 N이 주어지고, 다음 줄부터 N개씩 N개의 줄에 걸쳐 10이하의 자연수가 주어진다. 3<=N<=13
 

 

[출력]

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

 

 

 

 

 

풀이)

 

def recur(a, b, total):
    global ans
 
    di = [1, 0]
    dj = [0, 1]
 
    # 가지치기 
    if total > ans:
        return
    
    # 목적지에 도달했을 때
    if a == n - 1 and b == n - 1:
        if total > 14:
            ans = min(total, ans)
        return
 
    for i in range(2):
        x = a + di[i]
        y = b + dj[i]
        if -1 < x < n and -1 < y < n:
            recur(x, y, total + li[x][y])
 
T = int(input())
for _ in range(T):
    n = int(input())
    li = [list(map(int, input().split())) for i in range(n)]
    ans = 1 << 50
    recur(0, 0, li[0][0])
    print(f"#{_ + 1} {ans}")

---

문제 출처 : https://swexpertacademy.com/main/main.do

SW Expert Academy

※ SW Expert 아카데미는 원칙적으로 문제를 무단 복제하는 것을 금지합니다.

학습용으로 문제를 가져왔으나, 문제가 될 시 수정 및 삭제하겠습니다.