[SWEA] 5188. 최소합 - Python

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

SW Expert Academy

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

맨 왼쪽 위에서 오른쪽 아래까지 이동할 때, 지나는 칸에 써진 숫자의 합계가 최소가 되도록 움직였다면 이때의 합계가

 

얼마인지 출력하는 프로그램을 만드시오.

1	2	3
2	3	4
3	4	5

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

 

아도 된다.

 

< ❓ 생각 >

< 💻 코드 >

# (r,c) : 현재 위치, s : 지나온 길 숫자 합
def check(r,c,s):
    global min_sum
    # 도착?
    if r == N-1 and c == N-1:
        if min_sum > s:
            min_sum = s
        return
    
    # 최솟값을 구하는 것이니 이미 이전 최솟값보다 크면 계산 필요X
    if s > min_sum: 
        return
    
    # 이동
    for dr,dc in [[0,1],[1,0]]:
        # 범위 내
        if 0<=r+dr<N and 0<=c+dc<N:
            check(r+dr,c+dc,s+arr[r+dr][c+dc])

# 테스트 케이스 개수
T = int(input())
for tc in range(1,T+1):
    # N*N 숫자 판
    N = int(input())
    arr = [list(map(int,input().split())) for _ in range(N)]

    min_sum = 1000000000
    check(0,0,arr[0][0])

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

< ❗ 느낀 점 >

재귀가 점점 익숙해져간다!!!