[알고리즘] 프로그래머스 - 정수 삼각형

1. 문제

정수 삼각형

 

2. 접근

0,0	--	--	--	--
1,0	1,1	--	--	--
2,0	2,1	2,2	--	--
3,0	3,1	3,2	3,3	--
4,0	4,1	4,2	4,3	4,4

1. 특정 칸에 올수 있는 것은 바로위와 위의 왼쪽이다. -> ( (2,1) 에 올 수 있는값은 (1,0) 와 (1,1 ) 이다 )

2. 내려온 값 + 원래 있던값 -> ( (2,1) 에 올 수 있는값은 => (2,1) +  max( (1,0) ,(1,1 )) 이다 )

3. 맨 마지막 줄에서 가장 큰값을 출력하면 된다

* left_ up , up 구별은 2중 for문에서 2번째 반복문의 값이 0 이면 left_up, i == j 이면, up 이다

 

3. 풀이

# 정수 삼각형
import sys
input = sys.stdin.readline

n = int(input())

dp = []
for i in range(n):
    dp.append(list(map(int, input().split())))

for i in range(1, n):
    for j in range(i+1):
        if j == 0:
            left_up = 0
        else:
            left_up = dp[i-1][j-1]

        if j == i:
            up = 0
        else:
            up = dp[i-1][j]

        dp[i][j] += max(left_up, up)

print(max(dp[n-1]))