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

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

프로그래머스

과정 : 

문제에서 찾고자 하는 것 : 삼각형의 꼭대기에서 바닥까지 이어지는 경로 중, 거쳐간 숫자의 합이 가장 큰 경우

1. triangle 와 동일한 구조의 리스트인 sum_temp 리스트를 모두 값을 0으로 초기화하여 만든다.

2. sum_temp[0][0] 값을 삼각형의 꼭대기 값 (triangle[0][0])으로 변경한다.

3. i > 1 일때 sum_temp[i][j] 값을  sum_temp[i-1][j-1 or j] 값 + triangle[i][j] 값으로 변경한다.

이때, sum_temp[i-1][j-1 or j] 는 sum_temp[i-1][j-1] 와  sum_temp[i-1][j] 중에 큰값을 선택하여 결정한다.

예를 들면 sum_temp[2][1] = max(sum_temp[1][0], sum_temp[1][1] ) + triangle[2][1] 이 되고 sum_temp[2][1] = max(10, 15) + 1 으로 sum_temp[2][1]은 16이 된다.

4. j = 0 일때 sum_temp[i-1][j-1]의 값은 없으므로 ( sum_temp 왼쪽위의 값이 없음 )

sum_temp[i][j] = sum_temp[i-1][j] + triangle[i][j] 이 되고 (ex. sum_temp[2][0] = 10 + 8)

5. j = len(sum_temp[i]-1) 일때 즉 j가 맨 끝 줄일때 sum_temp[i-1][j] 의 값은 없으므로 ( sum_temp 오른쪽위의 값이 없음 )

sum_temp[i][j] = sum_temp[i-1][j-1] + triangle[i][j] 이 된다 (ex. sum_temp[2][2] = 15 + 0)

6. sum_temp의 맨 마지막 줄에 " 삼각형의 꼭대기에서 바닥까지 이어지는 경로 중, 거쳐간 숫자들의 합들" 이 계산되고 이중 max값이 가장 큰 합이다. 

def solution(triangle):
    answer = 0
    sum_temp = []
    
    #sum_temp : 주어진 triangle 리스트와 동일한 구조의 리스트, 값은 0으로 초기화
    for i in range(len(triangle)):
        sum_temp.append([])
        for j in range(len(triangle[i])):
            sum_temp[i].append(0)
    
    for i in range(len(triangle)):
        for j in range(len(triangle[i])):
            if i == 0:
                sum_temp[i][j] = triangle[i][j]
            elif j == 0: #j 가 0이면 sum_temp 왼쪽위의 sum값이 없기때문에 오른쪽위의 값과 현재 원소 값을 더해준다
                sum_temp[i][j] = sum_temp[i-1][j] + triangle[i][j]
            elif j == len(triangle[i])-1:  #j가 라인의 가장 끝값이면 sum_temp 오른쪽위의 sum값이 없기때문에 왼쪽위의 값과 현재 원소 값을 더해준다
                sum_temp[i][j] = sum_temp[i-1][j-1] + triangle[i][j]
            else: #오른쪽 위의 sum 값과 왼쪽위의 sum값중 큰값을 현재 원소 값에 더해준다
                sum_temp[i][j] = max(sum_temp[i-1][j-1],sum_temp[i-1][j]) + triangle[i][j]
                          
    answer = max(sum_temp[len(triangle)-1])
    return answer