Notice
Recent Posts
Recent Comments
«   2024/11   »
1 2
3 4 5 6 7 8 9
10 11 12 13 14 15 16
17 18 19 20 21 22 23
24 25 26 27 28 29 30
Tags
more
Archives
Today
Total
관리 메뉴

No Limitation

[DP] 정수 삼각형 - 프로그래머스 본문

프로그래밍

[DP] 정수 삼각형 - 프로그래머스

yesungcho 2022. 2. 2. 18:22

https://programmers.co.kr/learn/courses/30/lessons/43105?language=python3 

 

코딩테스트 연습 - 정수 삼각형

[[7], [3, 8], [8, 1, 0], [2, 7, 4, 4], [4, 5, 2, 6, 5]] 30

programmers.co.kr

 

Fact Finding


  • Index를 이용해 해당 노드 별 max값을 저장한 memo 이용
  • Recursion을 이용하여 노드 탐색

 

def depth_search(triangle, start, i, j, memo = {}, sums1=0, sums2=0) :
    if (i, j) in memo :
        return memo[(i, j)]
    if i == len(triangle):
        return max(sums1, sums2)
    sums1 = depth_search(triangle, start, i+1, j, memo) + triangle[i][j]
    sums2 = depth_search(triangle, start, i+1, j+1, memo) + triangle[i][j]
    memo[(i, j)] = max(sums1, sums2)
    return memo[(i, j)]

def solution(triangle):
    start = triangle[0][0]
    answer = 0
    answer = depth_search(triangle, start, 0, 0)
    return answer