정수 삼각형 문제 보러가기

문제 설명

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

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

제한 사항

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

입출력 예

문제 해결 과정

DP 문제라는 것을 알고 해결하려고 했지만 사실 DP로는 해결 과정을 생각하지 못했다.
전날 한시간 가량 고민하고 오늘도 한시간 정도 생각을 했지만 해결 과정을 찾지 못해 블로그를 참고했다.

위에서 아래로 내려가는 방법도 있고, 아래에서 위로 올라가는 방법도 있었다.
나는 처음에 아래에서 위로 올라가는 방법을 고민하고 있어서 그 방법을 참고했다.

밑에서 부터 더해가는 방법을 선택하는 것인데, 주어진 예시를 확인해보자.
맨 밑의 숫자들은 [4, 5, 2, 6, 5]가 있고 그 위에는 [2, 7, 4, 4]가 있다.
그 위에다가 밑의 숫자들을 더해야하는데, 2(index 0번째)는 그 밑의 4(index 0번째)와 5(index 1번째)를 더할 수 있다. 그 중의 큰 값을 찾아 2에다가 더하면 된다. 요약하면 triangle[i][j]에는 triangle[i+1][j]와 triangle[i+1][j+1] 중 큰 값을 찾아 더하는 방식으로 올라가면 된다.

최종 코드

def solution(triangle):

    floor = len(triangle) - 1  

    while floor > 0:  
        for i in range(floor):  
            triangle[floor-1][i] += max(triangle[floor][i], triangle[floor][i+1])
        floor -= 1  

    return triangle[0][0]

참고 블로그

https://velog.io/@ssulee0206/%ED%94%84%EB%A1%9C%EA%B7%B8%EB%9E%98%EB%A8%B8%EC%8A%A4-%EC%A0%95%EC%88%98-%EC%82%BC%EA%B0%81%ED%98%95%ED%8C%8C%EC%9D%B4%EC%8D%AC