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

Python3, 동적 프로그래밍

문제

제한 사항

입출력 예시

나의 풀이 (시도)

• [i][j] 라고 가정할 때, i는 1씩 커지고 j는 j-1과 같거나 1 커짐

주요 포인트

더해진 값을 누적값으로 나타낸 후 바꿀 수 있는 값 중 가장 큰 값을 선택함

        7
      10  15
    18  16  15
  20  25  20  19
24  30  27  26  24

배열 맨 앞 요소는 [i-1][j]랑 더함 ([7][3,8]일 때, [1][0]이랑 [0][0]이랑 더함)
배열 맨 뒤 요소는 [i-1][j-1]이랑 더함 ([10, 15][8, 1, 0]일 때, [2][2]이랑 [1][1]이랑 더함)
배열 중간 요소는 [i-1][j-1]과 [i-1][j] 중 큰 값을 더함

최종 코드

def solution(triangle):
    answer = 0

    # [i][j] i는 하나씩 커지고, j는 j-1과 같거나 1 커짐
    
    # [1][0] 부터 [0][0] 과 더할 거임
    for i in range(1, len(triangle)):
        for j in range(i+1):
            # 각 배열에 맨 앞 요소는
            if j == 0:
                # i-1이랑 더함
                triangle[i][j] += triangle[i-1][j]
            # 각 배열 맨 뒤 요소는
            elif j == i:
                # i, j 모두 1 작은 거랑 더함
                triangle[i][j] += triangle[i-1][j-1]
            # 중간 요소는
            else:
                # 둘 중 큰 값이랑 더함
                triangle[i][j] += max(triangle[i-1][j-1], triangle[i-1][j])
        
    # 마지막에 담긴 결과값 중 가장 큰 값 출력
    answer = max(triangle[-1])
    return answer