[프로그래머스] 정수 삼각형 (파이썬)

문제 링크

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

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

 

문제풀이

삼각형의 경로를 지나면서 최대값을 가지는 경로를 구하는 문제이다.

삼각형 트리안에 들어가는 값들은 0보다 크거나 같은 정수이기 때문에, 맨 아랫줄 삼각형의 누적값들 중 최대값을 고르면 되는 문제이다.

 

Sum(i,j) = V(i,j) + max(Sum(i-1, j-1), Sum(i-1, j)) 라는 점화식을 이용해 풀면 되는데,

i, j 값이 오바되지 않도록 예외처리만 신경써주면 쉬운 문제이다. 

 

시간복잡도

n 층의 n 개의 원소들은 각각 비교를 2번 씩 진행하므로, 2 * n 의 계산을 진행하며

위와같은 연산을 하므로 결국 시간복잡도는 O(n^2) 이다.

 

소스코드

import copy;

def solution(triangle):
    value = copy.deepcopy(triangle);
    height = len(triangle);
    
    for i in range(1, height):
        for k in range(0, i + 1):
            if (k == 0):
                left = 0;
            else:
                left = value[i-1][k-1];
            
            if (k == i):
                right = 0;
            else:
                right = value[i-1][k];
            
            value[i][k] = triangle[i][k] + max(left, right);
    return max(value[height - 1]);