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

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

프로그래머스

 

문제설명

 

 

 

위와 같은 삼각형의 꼭대기에서 바닥까지 이어지는 경로 중, 거쳐간 숫자의 합이 가장 큰 경우를 찾아보려고 합니다. 아래 칸으로 이동할 때는 대각선 방향으로 한 칸 오른쪽 또는 왼쪽으로만 이동 가능합니다. 예를 들어 3에서는 그 아래칸의 8 또는 1로만 이동이 가능합니다.

 

삼각형의 정보가 담긴 배열 triangle이 매개변수로 주어질 때, 거쳐간 숫자의 최댓값을 return 하도록 solution 함수를 완성하세요.

 

문제 해결 방법

 

triangle을 순회할때, n번째 리스트의 각 원소를 기준으로 n-1번째 리스트에서 자신이 거쳐올 수 있었던 원소 후보 중에서 큰 값을 자신과 더해나가면 된다. 

 

 

코드 구현

 

def solution(triangle):
    answer = 0
    
    for idx, i in enumerate(triangle):
        if idx == 0:
            continue
            
        for cnt, j in enumerate(i):
            if cnt == 0:
                i[cnt] = triangle[idx-1][cnt] + i[cnt]
            elif cnt == len(i)-1:
                i[cnt] = triangle[idx-1][cnt-1] + i[cnt]
            else:
                if triangle[idx-1][cnt-1] > triangle[idx-1][cnt]:
                    i[cnt] = triangle[idx-1][cnt-1] + i[cnt]
                else:
                    i[cnt] = triangle[idx-1][cnt] + i[cnt]
        if len(triangle)-1 == idx:
            answer = max(triangle[idx])
    
    
    return answer

 

시간/공간 복잡도

 

O(n^2)

 

최적화 및 개선

 

따로 하지 않음

 

어려웠던 점

 

재귀함수로 구현해야하나 스택으로 구현해야하나 고민했지만 굳이 그렇게 구현할 필요 없었다.