💻코딩테스트 문제풀이12

Chapter10. 동적 프로그래밍

[문제40] 정수 삼각형 - Level3

		7
	  3  8
	8   1   0
  2   7   4   4
4	5	2	6	5

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

예를 들어 3에서는 그 아래칸의 8 또는 1로만 이동 가능

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

[제한사항]

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

[코드작성]

• 계산 결과를 계속 쌓을 배열 생성

def solution(triangle):
	dp = [[0, *t, 0] for t in triangle]

• 맨 꼭대기부터 시작해 하나씩 내려가면서 계산

for i in range(1, len(triangle)):
	for j in range(1, i+2):
    	dp[i][j] += max(dp[i-1][j-1], dp[i-1][j])

• 결과 중 가장 큰 값을 반환

return max(dp[-1])

[전체코드]

def solution(triangle):
	dp = [[0, *t, 0] for t in triangle]
    for i in range(1, len(triangle)):
		for j in range(1, i+2):
    		dp[i][j] += max(dp[i-1][j-1], dp[i-1][j])
        
	return max(dp[-1])

[다른 문제풀이]

• 높이 지정

def solution(triangle):
	height = len(triangle) - 1

• 맨 아래부터 시작해 하나씩 올라가면서 계산

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

• 결과 배열의 가장 첫 번째 원소를 반환

return triangle[0][0]

[전체코드2]

def solution(triangle):
	height = len(triangle) - 1
    
    while height > 0:
      for i in range(height):
          triangle[height-1][i] += max([triangle[height][i], triangle[height][i+1]])
      height -= 1
    
    return triangle[0][0]