문제

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

입력

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

출력

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

풀이

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

top-down 방식으로 문제 해결!

정답 풀이

• dy 라는 다이나믹 배열 생성
• dy[N-1][N-1] 부터 최솟값 찾아가면서 값 누적한다.
• 추가 조건은 행이나 열이 0일때 가는 경로 설정
• 시간 단축을 위해 이미 값을 구한 것은 return 시켜 버린다.
  

정답 코드 비교

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

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

def DFS(x,y):
    # 아래 메모이제이션 해줬으므로 여기서 cut이 가능하다 -> 시간단축
    if dy[x][y] > 0:
        return dy[x][y] # 이미 값을 구한것은 return 한다.
    if x == 0 and y == 0: # 재귀의 출발지점
        return arr[0][0]
    else:
        #if y == 0:
        #    return DFS(x-1,y)+arr[x][y]
        #elif x == 0:
        #    return DFS(x,y-1)+arr[x][y]
        #else:
        #    return min(DFS(x-1,y), DFS(x,y-1))+arr[x][y] 
        # 여기까지 이렇게 하면 TimeLimit 난다. 
        # 왜냐하면 reutrn 하면서 시간 오래걸림, 값을 기록해 주는 메모이제이션 필요
        
        if y == 0:
            dy[x][y] = DFS(x-1,y)+arr[x][y]
        elif x == 0:
            dy[x][y] = DFS(x,y-1)+arr[x][y]
        else:
            dy[x][y] = min(DFS(x-1,y),DFS(x,y-1))+arr[x][y] 
        return dy[x][y]


if __name__ == "__main__":
    N = int(input())
    arr = [list(map(int,input().split())) for _ in range(N)]
    dy = [[0]*N for _ in range(N)]
    print(DFS(N-1,N-1)) # 도착지점부터 시작

코멘트

끝에서 부터 최솟값을 구해 나가는 것! 그것이 결국 DFS로, dy[0,0] 부터 채워 나가게 된다. 무엇보다 이미 구한 값은 return 하므로 더 깊이 DFS할 필요가 없어진다.