Hama Develop

프로그래머스-정수 삼각형, 파이썬

February 21, 2020

출처

문제 설명

그림

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

풀이

순간순간의 합이 중요한게 아니라 전체의 합이 중요한 문제다.

끝가지 가보기 전에는 뭐가 제일 큰지 미지수 이므로 모든 경우의 수를 다 계산해 보고 그 중에서 가장 큰 값을 반환 해야 한다.

삼각형의 한층 한층을 단계라고 칭하겠다.

삼각형의 각 숫자는 다음 단계에서 자신의 순서 i 와 i+1에만 접근할 수 있다.

삼각형 위에서부터 차근차근 더해가면서 내려와서 맨 마지막에 나오는 값중 최댓값을 반환하면 된다.

단, 맨 왼쪽에 있는 숫자와 맨 오른쪽에 있는 숫자는 선택권이 없다. 왼쪽끝은 무조건 이전 숫자리스트의 0번을, 오른쪽 끝은 이전 숫자 리스트의 끝번을 더해야 한다.

이렇게 구해진 마지막 층의 숫자중 최댓값을 리턴해 주면 된다.

이를 함수로 구현하면 아래와 같다.

def solution(triangle):
    answer =0
    
    for i in range(1, len(triangle)): #이후 연산에 i-1시점의 값을 더하기 때문에 0부터 시작이 아니라 1부터 시작을 한다. 
        for j in range(i+1): # 0번 층일때 원소의 개수는 1이다. 1번층일때 원소의 개수는 2다. 그니까 i+1개를 해야 답이 맞다. 모든 원소를 순회해야 하기 때문이다.
            if j == 0:
                triangle[i][j] += triangle[i-1][0]
            elif j == i:
                triangle[i][j] += triangle[i-1][-1]
            else:
                triangle[i][j] += max([triangle[i-1][j], triangle[i-1][j-1]])
    return max(triangle[len(triangle)-1])