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

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

분류 : Dynamic Programming

사용언어 : Python3

문제 분석

삼각형 모양으로 구성되어 있는 수를 2차 배열의 모양으로 입력받는다.

위에서 아래로 내려가며 인접한 수들의 합을 구해가며 제일 아래에서 가장 큰 수를 구하는 문제이다.

문제 접근

for문을 이용하여 삼각형의 높이 - 1 만큼 순회한다.

이 때 다음 줄(i+1)을 기준으로 위 줄(i)과 비교를 수행하는데 이 때 세가지 경우가 나타나게 된다.

1. 가장 왼쪽에 위치한 숫자 (첫번째 index)

위 줄의 첫 번째 숫자와 합을 현재 값으로 갱신한다.

2. 가장 오른쪽에 위치한 숫자 (마지막 index)

위 줄의 마지막 숫자와 합을 현재 값으로 갱신한다.

3. 그 사이에 위치한 숫자

위에 위치한 숫자 두 개의 합 중 더 큰 값(max)을 현재 값으로 갱신한다.

위의 과정을 계속하여 수행하며 값을 갱신하면 가장 마지막에는 현재 위치에서 얻을 수 있는 가장 큰 값이 나타나게 된다.

이 값에 대하여 max함수를 통하여 최대 값을 구하도록 하였다.

문제 풀이 (소스 코드)

def solution(triangle):
    answer = 0
    for i in range(0, len(triangle) - 1):
        sub = triangle[i]
        for j in range(len(triangle[i+1])):
            if j == 0:
                triangle[i+1][j] = sub[j] + triangle[i+1][j]
            elif j == len(triangle[i+1]) - 1:
                triangle[i+1][j] = sub[j-1] + triangle[i+1][j]
            else:
                triangle[i+1][j] = max(triangle[i+1][j] + sub[j-1], triangle[i+1][j] + sub[j])
    
    answer = max(triangle[-1])
    return answer