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

문제 설명

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

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

---

제한사항

• 삼각형의 높이는 1 이상 500 이하입니다.
• 삼각형을 이루고 있는 숫자는 0 이상 9,999 이하의 정수입니다.

---

입출력 예

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

---

나의 코드

각 층을 돌며 최댓값을 저장하기로했다.

기존 정수 삼각형 [7], [3, 8], [8, 1, 0], [2, 7, 4, 4], [4, 5, 2, 6, 5] ↓ 최댓값 삼각형 [7], [10, 15], [18, 16, 15], [20, 25, 20, 19], [24, 30, 27, 26, 24]

 

def solution(triangle):
    answer = 0
    for i in range(len(triangle)):		#triangle높이만큼 순회
        for j in range(len(triangle[i])):		#각 층의 리스트 길이만큼 순회
            if i==0 and j==0:		#맨 꼭대기 층이면 
                continue	#패스하기
            elif j==0:		#각 층의 첫번째 요소라면 윗층의 첫번째 요소만 더할수있으므로
                triangle[i][j]+=triangle[i-1][j]	#윗층의 첫 번째 요소 더하기
            elif j==len(triangle[i])-1:		#각 층의 마지막 요소라면 윗층의 마지막 요소만 더할수있으므로
                triangle[i][j]+=triangle[i-1][j-1]		#윗층의 마지막 요소 더하기
            else:		#모두 해당안된다면(리스트 중간에 있는 요소라면)
                triangle[i][j]+=max(triangle[i-1][j-1],triangle[i-1][j])	#윗층(i-1)의 본인y인덱스-1(j-1) 요소와 본인y인덱스(j) 요소중 최댓값을 더하기
    answer=max(triangle[len(triangle)-1])		#마지막 층에는 각 요소까지 더했을때의 최댓값이므로 그 중 제일 최댓값을 구해줌
    return answer