[SWEA][D3][#11802] 완전검색_최소합

출처

• SW Expert Academy

학습용 포스트입니다. 본 포스트가 문제가 될 시 수정 또는 삭제하겠습니다.

문제

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

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

그림 생략

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

입력

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

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

출력

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

예제

입력

3
3
1 2 3
2 3 4
3 4 5
4
2 4 1 3
1 1 7 1
9 1 7 10
5 7 2 4
5
6 7 1 10 2
10 2 7 5 9
9 3 2 9 6
1 6 8 2 9
8 3 8 2 1

출력

#1 15
#2 18
#3 33

My Sol

T = int(input())
for tc in range(1, T+1):
    N = int(input())
    mat = [list(map(int, input().split())) for _ in range(N)]
    ans = [[0]*N for _ in range(N)]
    ans[0][0] = mat[0][0]

    for i in range(1, N):
        ans[i][0] = mat[i][0] + ans[i-1][0]
    for j in range(1, N):
        ans[0][j] = mat[0][j] + ans[0][j-1]

    for i in range(1, N):
        for j in range(1, N):
            ans[i][j] = mat[i][j] + min(ans[i][j-1], ans[i-1][j])

    print(f'#{tc} {ans[N-1][N-1]}')

memoization과 재귀를 이용한 간단한 DP 문제였다. 처음에는 백트래킹으로 문제를 풀었는데 연산 시간이 아쉬워서 고민해보니 DP를 적용하기 정말 좋은 구조였다. 점화식이 쉽게 보였다.

결과

PASS