본문 바로가기
혼자 공부하는 것들/알고리즘

120. Triangle (DP, DFS로 풀어보자!)

by applepick 2022. 7. 3.
반응형

https://leetcode.com/problems/triangle/

 

Triangle - LeetCode

Level up your coding skills and quickly land a job. This is the best place to expand your knowledge and get prepared for your next interview.

leetcode.com

 

문제:

Given a triangle array, return the minimum path sum from top to bottom.

For each step, you may move to an adjacent number of the row below. More formally, if you are on index i on the current row, you may move to either index i or index i + 1 on the next row.

삼각형 모양의 배열을 입력받아 순차적으로 내려가면서 i, i+1중에 이동하면서 최솟값을 찾아 더해줍니다. 처음 문제를 봤을 때 DP로 풀어야 할 것 같아 점화식을 먼저 찾아보았습니다.  

간단하게 보자면 윗 레벨의 위치에서 바로 아래 레벨의 i, i+1번째 중 최소값을 찾아 더 해주면 되겠네요 

def minimumTotal(self, triangle: List[List[int]]) -> int:
        # DP로 풀기~
        n = len(triangle)
        
        dp = [[0]*(n+1) for _ in range(n+1)]
        
        for level in range(n-1,-1,-1):
            for i in range(level+1):
                dp[level][i] = triangle[level][i] + min(dp[level+1][i], dp[level+1][i+1])
        
        return dp[0][0]

bottom -> top으로 올라가면서  + 해준 값을 상위 레벨의 값을 더 해주고 최종적으로 맨꼭대기에 있는 것을 반환해주면 됩니다.

 

DFS로 풀어보면

def minimumTotal(self, triangle: List[List[int]]) -> int:
    @cache
    def dfs(level, i):
        return 0 if level >= len(triangle) else triangle[level][i]+ min(dfs(level+1,i), dfs(level+1,i+1))
    return dfs(0,0)

이런 식으로 풀어볼 수 있겠네요

 

@cache를 사용해주지 않으면

이처럼 타임아웃 납니다. DFS 인접 행렬로 풀었을 경우 시간 복잡도가 O(N^2)이기 때문에 문제에서 제한한 O(N)에 미치지 못합니다. 하지만 @cache를 사용하면 캐싱을 통해 메모이제이션 기법을 사용하여 최적화를 하여 DFS로 풀 수 있습니다. (근데 이렇게 풀어도되나?...)

반응형

댓글