📌문제
https://programmers.co.kr/learn/courses/30/lessons/43105
🎖️난이도
Level 3
✔️풀이
# sol1
def solution(triangle):
i_len = len(triangle) # 5
for i in range(1, i_len):
for j in range(i+1):
# i++
if j == 0:
triangle[i][j] += triangle[i-1][0]
continue
# i++, j++
elif i == j:
triangle[i][j] += triangle[i-1][j-1]
continue
# i++ or i++, j++
triangle[i][j] = max(triangle[i-1][j-1]+triangle[i][j], triangle[i-1][j]+triangle[i][j])
'''
tmp_max = 0
for j in range(i_len):
if tmp_max > triangle[i_len-1][j]:
continue
tmp_max = triangle[i_len-1][j]
return tmp_max
'''
return max(triangle[i_len-1])
# sol2
solution = lambda t, l = []: max(l) if not t else solution(t[1:], [max(x,y)+z for x,y,z in zip([0]+l, l+[0], t[0])])
'[ 알고리즘 ] > DP' 카테고리의 다른 글
[프로그래머스] 도둑질 (0) | 2022.06.29 |
---|---|
[프로그래머스] 등굣길 (0) | 2022.06.29 |
[프로그래머스] N으로 표현 (0) | 2022.06.29 |
[백준] 17979. What's Mine is Mine (0) | 2022.06.29 |
[백준] 17968. Fire on Field (0) | 2022.06.29 |