120. Triangle

120. Triangle

 

https://youtu.be/OM1MTokvxs4?si=TThNXJkoqEIPcJsj

 

 

class Solution:
    def minimumTotal(self, triangle: List[List[int]]) -> int:
        # 삼각형의 아래에서 위로 계산
        """
        # bottom -> up 으로 가면서, min 계산

        # 원래는 len(triangle)-1 시작이겠지만,  
        # len(triangle)-1 이 마지막 단계니깐. 
        # len(triangle)-2 부터 시작
        """
        for row in range(len(triangle) - 2, -1, -1):
            for col in range(len(triangle[row])):
                # 현재 값과 아래 줄에서 가능한 두 경로 중 작은 값을 더함
                triangle[row][col] += min(triangle[row + 1][col], triangle[row + 1][col + 1])

        # 최종 결과는 삼각형의 꼭대기 값에 저장됨
        return triangle[0][0]

 

동작 방식

1. 아래에서 위로 계산:
   • 삼각형의 아래에서 두 번째 줄부터 시작하여, 각 값을 아래 줄의 가능한 두 경로 중 작은 값을 더하여 업데이트합니다.
2. 제자리 연산:
   • 별도의 추가 메모리 공간을 사용하지 않고, 삼각형 데이터를 직접 수정하며 계산합니다.
3. 최소 경로 합:
   • 모든 계산이 끝나면 삼각형의 첫 번째 값(triangle[0][0])에 최소 경로 합이 저장됩니다.

 

2번째: 그냥 품: 2025.01.03

class Solution:
    def minimumTotal(self, triangle: List[List[int]]) -> int:
        # 아래부터 .. 
        # 루프 돌면서 검색하는 것이..        
        # 답은 새로운 triangle[0][0] 에서
        """
        # **별도의 메모리 사용하지 않아서 O(n) 임**
        """

        # 원래 뒤에서 부터면, len(triangle)-1 이지만,
        # 제일 아래줄은.. 계산은 포함하나, 루프에서는 제외 할 예정이므로
        # len(triangle)-2 부터
        for r in range(len(triangle)-2, -1, -1):
            for c in range(len(triangle[r])):
               triangle[r][c] += min(triangle[r+1][c], triangle[r+1][c+1]) 
        return triangle[0][0]