[LeetCode]Triangle

2024. 4. 15. 23:52·SW개발/코딩테스트

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

 

LeetCode - The World's Leading Online Programming Learning Platform

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

 

문제 분석

triangle 리스트가 주어질 때 위에서부터 아래로 이동시 가장 최소가 되는 경로의 합을 구하는 문제입니다.

 

처음 시도한 답안

class Solution:
    def minimumTotal(self, triangle: List[List[int]]) -> int:
        triangle_len = len(triangle)

        for i in range(1, triangle_len):
            for j in range(i+1):
                if j == 0:
                    triangle[i][j] = triangle[i][j] + triangle[i-1][j]
                elif j == i:
                    triangle[i][j] = triangle[i][j] + triangle[i-1][j-1]
                else:
                    triangle[i][j] = triangle[i][j] + min(triangle[i-1][j-1], triangle[i-1][j])


        return min(triangle[-1])

접근 방법

  1. DP를 활용해 풀이할 수 있는 문제입니다.
  2. 각 높이별로 존재하는 숫자만큼 이중 순회를 반복합니다.
    1. 만약 가장 왼쪽에 있는 숫자라면 현재 숫자와 i-1, j에 있는 숫자를 더합니다.
    2. 만약 가장 오른쪽에 있는 숫자라면 현재 숫자와 i-1, j-1에 있는 숫자를 더합니다.
    3. 그 외의 경우에는 현재 숫자에서 i-1,j-1 혹은 i-1,j 중 작은 값과 숫자를 더합니다.
  3. 반복을 마치면 마지막 열에 가장 적은 숫자가 최소 경로의 합이 됩니다.

Top - Bottom 방식으로 숫자를 누적해나가면서 쉽게 풀이할 수 있는 DP 기본 문제입니다.

 

728x90

'SW개발 > 코딩테스트' 카테고리의 다른 글

[LeetCode]House Robber  (0) 2024.04.17
[LeetCode]Maximal Square  (0) 2024.04.16
[백준]ABCDE - 13023번  (0) 2024.04.14
[LeetCode]Unique Binary Search Trees  (0) 2024.04.13
[LeetCode]Find All Groups of Farmland  (0) 2024.04.12
'SW개발/코딩테스트' 카테고리의 다른 글
  • [LeetCode]House Robber
  • [LeetCode]Maximal Square
  • [백준]ABCDE - 13023번
  • [LeetCode]Unique Binary Search Trees
Leffe_pt
Leffe_pt
개발자로서 성장하면서 배워온 지식과 경험을 공유하는 공간입니다.
  • Leffe_pt
    Leffe's tistory
    Leffe_pt
  • 전체
    오늘
    어제
    • 분류 전체보기 (307)
      • SW개발 (303)
        • 코딩테스트 (172)
        • 개발이야기 (23)
        • IT 용어 (17)
        • Python (22)
        • Django (46)
        • Flask (2)
        • Database (1)
        • SQLAlchemy (0)
        • Javascript (5)
        • Linux, Unix (3)
        • JAVA (2)
        • Spring (10)
      • 회고 (4)
      • 사진 (0)
  • 블로그 메뉴

    • 홈
    • 태그
    • 방명록
  • 링크

  • 공지사항

  • 인기 글

  • 태그

    음식
    django
    플레이스토어
    Contributor
    배달비 공유
    오픈소스
    g
    컨트리뷰터
    배달
    어플리케이션
    배공파용
    라이프 스타일
    트리 #AVL #알고리즘 #자료구조
  • 최근 댓글

  • 최근 글

  • hELLO· Designed By정상우.v4.10.3
Leffe_pt
[LeetCode]Triangle
상단으로

티스토리툴바