문제
접근
동적계획법이라면 동적계획법인 문제이다.
꼭대기에서 시작해서 아래로 내려가면서 현재 위치에서 가장 큰값을 찾으면된다.
좌,우 끝부분은 자기자신에 바로 위를 더하면 되고, 중앙에 위치한 부분들은 자기와 연결된 위에 둘 중 큰값을 더해주면 된다.
코드
- 파이썬 코드
1
2
3
4
5
6
7
8
9
10
11
12
13
def solution(triangle):
for i in range(len(triangle)):
if i == 0:
continue
for j in range(len(triangle[i])):
if j == 0:
triangle[i][j] += triangle[i-1][j]
elif j == len(triangle[i])-1:
triangle[i][j] += triangle[i-1][j-1]
else:
triangle[i][j] += max(triangle[i-1][j], triangle[i-1][j-1])
answer = max(triangle[-1])
return answer