[코드트리] 정수 사각형 최대 합2, 최소 합

문제 

N×N 행렬이 주어졌을 때, (1,N)에서 시작하여 왼쪽 혹은 밑으로만 이동하여 (N,1)로 간다고 했을 때 거쳐간 위치에 적혀있는 숫자의 합을 최소로 하는 프로그램을 작성해보세요.

 

입력 형식 

첫째 줄에는 N이 주어집니다.

두 번째 줄 부터 N개의 줄에 각각 각 행에 해당하는 N개의 정수 값이 공백을 사이에 두고 주어집니다.

• 1≤N≤100
• 1≤ 행렬에 주어지는 숫자 ≤1,000,000

 

출력 형식 

가능한 최소 합을 출력합니다.

 

입출력 예제 

예제1 

입력:

3
5 2 1
1 9 1
1 8 9

출력:

10

 

---

오른쪽 위에서 왼쪽 아래로 한칸씩 감 

 

최대 합 

import sys
sys.stdin=open('input1.txt','r')


if __name__=="__main__":
    n=int(input())
    board = [list(map(int, input().split())) for _ in range(n)]

    dp=[[0 for _ in range(n)] for _ in range(n)]

    dp[0][n-1] = board[0][n-1]

    for i in range(1,n):
        dp[i][n-1] = dp[i-1][n-1] + board[i][n-1]
    
    for i in range(1,n):
        dp[0][n-1-i] = dp[0][n-1-(i-1)] + board[0][n-1-i]

    for i in range(1,n):
        for j in range(n-1-1,-1,-1):
            dp[i][j] = max(dp[i-1][j], dp[i][j+1]) + board[i][j]
    
    print(dp[n-1][0])

 

최소 합

import sys
sys.stdin=open('input1.txt','r')


if __name__=="__main__":
    n=int(input())
    board = [list(map(int, input().split())) for _ in range(n)]

    dp=[[0 for _ in range(n)] for _ in range(n)]

    dp[0][n-1] = board[0][n-1]

    for i in range(1,n):
        dp[i][n-1] = dp[i-1][n-1] + board[i][n-1]
    
    for i in range(1,n):
        dp[0][n-1-i] = dp[0][n-1-(i-1)] + board[0][n-1-i]

    for i in range(1,n):
        for j in range(n-1-1,-1,-1):
            dp[i][j] = min(dp[i-1][j], dp[i][j+1]) + board[i][j]
    
    print(dp[n-1][0])