[코드트리] 정수 사각형 최대 합1

 

문제

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

 

입력 형식 

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

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

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

출력 형식 

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

 

예제1 

입력:

3
1 2 3
3 2 1
4 2 1

 

출력:

11

 

예제2

입력:

3
1 3 2
3 4 5
4 2 1

 

출력:

14

 

---

백트래킹과 DP 문제인거 같다. 

그러나 백트래킹의 경우도 중복되는 계산이 발생하므로 DP로 푸는것이 가장 최적이다. 

 

 

백트래킹 방법 1 

import sys

def in_range(nx, ny):
    return 0<=nx<n and 0<=ny<n

dxs, dys = [1, 0], [0, 1]

def DFS(x, y):
    # 도착 지점에 도착하면 최대 합을 갱신해줍니다.
    if x == n-1 and y == n-1:
        return board[n - 1][n - 1]
    
    # 가능한 모든 방향에 대해 탐색해줍니다.
    max_sum = 0 # 주어진 숫자의 범위가 1보다 크기 때문에 항상 갱신됨이 보장됩니다.
    for dx, dy in zip(dxs, dys):
        nx = x+dx
        ny = y+dy
        
        if in_range(nx, ny):
            max_sum = max(max_sum, DFS(nx, ny) + board[x][y])
            
    return max_sum

if __name__=="__main__":
    n=int(input())

    board = [list(map(int, input().split())) for _ in range(n)]
                        
    print(DFS(0, 0))

 

백트래킹 방법 2

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

def in_range(nx, ny):
    return 0<=nx<n and 0<=ny<n

dxs, dys = [1, 0], [0, 1]


def DFS(x, y, sum):
    global max_sum
    
    # 도착 지점에 도착하면 최대 합을 갱신해줍니다.
    if x == n-1 and y == n-1:
        max_sum = max(max_sum, sum)
        return
    
    dxs, dys = [1, 0], [0, 1]
    
    # 가능한 모든 방향에 대해 탐색해줍니다.
    for dx, dy in zip(dxs, dys):
        nx = x+dx
        ny = y+dy
        
        if in_range(nx, ny):
            DFS(nx, ny, sum + board[nx][ny])


if __name__=="__main__":                       
    n = int(input())

    board = [list(map(int, input().split())) for _ in range(n)]
    max_sum = 0
    DFS(0, 0, board[0][0])
    print(max_sum)

 

---

백트래킹을 하는 과정에서 중복되는 계산을 DP (Memoization)을 활용하여 줄인다. 

백트래킹을 수행할 경우 동일한 위치를 중복하여 탐색하게 되어 불필요한 연산이 매우 많습니다. 

위 그림과 같이 시작점에서 시작하여 노란색 위치까지 가는데 '검정색 화살표'와 '파랑색 화살표'가 있다고 해보자. 

검정색 화살표로 표시된 경로로 이동하여 노란색 위치까지 도달한 뒤, 해당 위치에서 시작하여 회색으로 표시된 영역을 탐색하여 도착점까지의 최대합을 구했다고 생각해보자. 

이후에 파란색 화살표로 표시된 경로로 이동하여 노란색 위치에 도달한 후, 동일하게 회색으로 표시된 영역을 탐색하여 

도착점까지의 최대합을 구한다. 

백트래킹의 경우 중복이 굉장히 많다.  

위와 같은 비효율을 줄이기 위하여 DP (Memoization)을 활용하여 계산된 값을 저장한 뒤에 탐색을 하는 과정에서 이전에 이미 계산된 적 있는 경우 해당 값을 사용해준다. 따라서 (0,0)~(N-1,N-1) 내의 위치들을 단 한 번씩만 탐색하게 되므로 시간 복잡도는 O(N^2)가 된다. 

 

 

DP 방법 1 

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



def in_range(nx, ny):
    return 0<=nx<n and 0<=ny<n

dxs, dys = [1, 0], [0, 1]

def DFS(x, y):
    # 미리 계산된 적이 있는 경우 해당 값을 사용해줍니다.
    if memo[x][y] != UNUSED:
        return memo[x][y]
    
    # 도착 지점에 도착하면 최대 합을 갱신해줍니다.
    if x == n-1 and y == n-1:
        return board[n-1][n-1]

    
    # 가능한 모든 방향에 대해 탐색해줍니다.
    max_sum = 0 # 주어진 숫자의 범위가 1보다 크기 때문에 항상 갱신됨이 보장됩니다.
    for dx, dy in zip(dxs, dys):
        nx = x+dx
        ny = y+dy
        
        if in_range(nx, ny):
            max_sum = max(max_sum, DFS(nx, ny) + board[x][y])
        
    # 게산된 값을 memo 배열에 저장해줍니다.
    memo[x][y] = max_sum
    return max_sum

if __name__=="__main__":

    n = int(input())

    UNUSED = -1

    board = [list(map(int, input().split())) for _ in range(n)]
     
    memo = [[UNUSED for _ in range(n)] for _ in range(n)]



print(DFS(0, 0))

 

그러나 이방법 말고 점화식을 통해 Tabulation방식의 DP로 푸는 방법도 있다. 

 

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

def in_range(nx, ny):
    return 0<=nx<n and 0<=ny<n


def initialize():
    # 시작점의 경우 dp[0][0] = board[0][0]으로 초기값을 설정해줍니다
    dp[0][0] = board[0][0]
    
    # 최좌측 열의 초기값을 설정해줍니다.
    for i in range(1, n):
        dp[i][0] = dp[i-1][0] + board[i][0]
    
    # 최상단 행의 초기값을 설정해줍니다.
    for j in range(1, n):
        dp[0][j] = dp[0][j-1] + board[0][j]

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)]
        
        
    # 초기값 설정
    initialize()

    # 탐색하는 위치의 위에 값과 좌측 값 중에 큰 값에
    # 해당 위치의 숫자를 더해줍니다. 
    for i in range(1, n):
        for j in range(1, n):
            dp[i][j] = max(dp[i-1][j], dp[i][j-1]) + board[i][j]
            
    print(dp[n-1][n-1])

 

---

규칙을 못찾아 점화식을 못만들면 백트래킹으로 

찾으면 점화식으로 DP를 풀어보자