[프로그래머스lv.3] 정수 삼각형

programmers.co.kr/learn/courses/30/lessons/43105

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

---

풀이

 

깊이를 i 라고 봤을 때 i-1 번째 깊이엣 ㅓ어떤 숫자를 선택했느냐에 따라 결과값이 달라진다.

즉 dp 문제이다.

 

깊이를 i, i번째 배열에서의 인덱스를 j라고 해보자

 

i번째깊이의 j번째 수의 합의 최대값은 무엇일까?

답은 i-1번째 깊이의 j-1번째수까지의 최대값과 j번째수까지의 최대값중 큰 값 + i번째깊이의 j번째 수일 것이다.

 

dp[i][j] = i번째 깊이의 j번째 인덱스가 가지는 합의 최댓값이다.

 

즉

 

dp[i][j] = max(dp[i-1][j-1],dp[i-1][j]) + triangle[i][j]

 

---

시간복잡도

dp[i][j] 의 갱신이 j의 총합만큼 일어난다.

j = 1,2,3,4,.....n 이므로

시간복잡도는 O(j(j+1)//2)라고 볼 수 있으므로 O(N*2)이다. N은 500 이하이므로 여유있게 통과한다.

 

 

---

코드(바텀업)

def solution(triangle):
    dp = [[0 for i in range(502)] for j in range(502)]
    for i,tri in enumerate(triangle,start = 1):
        for j,t in enumerate(tri,start = 1):
            dp[i][j] = max(dp[i-1][j-1],dp[i-1][j]) + triangle[i-1][j-1]

    answer = max(dp[len(triangle)])

    return answer