Part7.7_동적프로그래밍(DynamicProgramming)_알리바바와 40인의 도둑(Bottom-Up)

문제

가장 높은 탑을 구하는 프로그램 만들자

입력

첫 번째 줄에는 자연수 N(1<=N<=20)이 주어진다.
두 번째 줄부터 계곡의 N*N 격자의 돌다리 높이(10보다 작은 자연수) 정보가 주어진다.

출력

첫 번째 줄에 (1, 1)출발지에서 (N, N)도착지로 가기 위한 최소 에너지를 출력한다.

풀이

• DFS 생각해서 x+1 과 y+1 하여 sum에 이차원 배열 값을 저장하였으나, 답은 맞지만 시간 limit,, 어떤 조건을 걸어줘야 할지 알아내지 못했다.
  

내가 생각한 코드

import sys
def input():
    return sys.stdin.readline().rstrip()

def DFS(x, y, sum):
    global N
    if x > N:
        return
    elif y > N:
        return
    elif x== N and y == N:
        res.append(sum)
        return

    else:
        DFS(x+1,y,sum+arr[x+1][y])       
        DFS(x,y+1,sum+arr[x][y+1])
      


if __name__ == "__main__":
    N = int(input())
    arr = [0 for _ in range(N)]
    res = []

    for i in range(N):
        arr[i] = list(map(int,input().split()))
        arr[i].insert(0,0)
        arr[i].append(0)
    arr.insert(0,[0]*(N+2))
    arr.append([0]*(N+2))

    DFS(1,1,arr[1][1])
    print(min(res))
  

정답 풀이

• 2차원 리스트를 하나 더 만들어서 dy 배열에 값을 저장한다.
• 도착점을 기준으로 어떻게 해야 최소로 올 수 있는지를 누적한다.
• 이를 위해 앞전에 0 행과 0열은 가질 수 있는 최솟값이 1개씩 이므로, 초기화 해준다.
  

정답 코드 비교

import sys
sys.stdin=open("input.txt","rt")

def input():
    return sys.stdin.readline().rstrip()

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

    dy = [[0]*N for _ in range(N)]
    dy[0][0] = arr[0][0]
    #0 행과 0열은 가질 수 있는 최솟값이 1개씩 이므로, 초기화 해준다.
    for i in range(N):
        dy[0][i] = dy[0][i-1]+arr[0][i]
        dy[i][0] = dy[i-1][0]+arr[i][0]
    for i in range(1, N):
        for j in range(1,N):
            dy[i][j] = min(dy[i-1][j],dy[i][j-1])+arr[i][j]
    print(dy[N-1][N-1])

코멘트

아 튜플 인덱스 0 으로 정렬할때는 굳이 lambda 안쓰고 sort 해도 되는구나