[프로그래머스/Python] 정수 삼각형

문제 정보

제목 : 정수 삼각형

난이도 : Lv.3

사용 언어 : Python

문제 링크

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

프로그래머스

 

문제 설명

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

---

나의 풀이

triangle 배열과 동일한 dp를 생성합니다. 그리고 dp의 꼭대기에 삼각형의 꼭대기 값을 저장합니다. 1부터 triangle의 길이만큼 반복하는 for 루프와 현재 행의 값들을 하나씩 접근하기 위한 이중 for 루프를 이용합니다. 순차적으로 접근하는 값을 기준으로 대각선 방향 위칸의 dp값을 구해 iNum과 더한 후 해당 dp에 저장합니다.

반복이 끝나면 dp의 제일 바닥 부분의 값중 최대값을 return합니다.

코드

def solution(triangle):
    answer = 0
    dp = [[0 for j in range(len(triangle[i]))] for i in range(len(triangle))]
    dp[0] = [triangle[0][0]]
    
    for i in range(1,len(triangle)):
        lenT = len(triangle[i-1])
        for j in range(0,len(triangle[i])):
            iNum = triangle[i][j]
            if j == 0 :
                dpNum1 = dp[i-1][0]
                dpNum2 = dp[i-1][0]
            else :
                dpNum1 = dp[i-1][j-1]
                dpNum2 = dp[i-1][j] if j < lenT else dp[i-1][lenT-1]
            dp[i][j] = max(dpNum1+iNum, dpNum2+iNum)
            
    answer = max(dp[-1])
    return answer