[Python] 프로그래머스(Lv2) - 정수 삼각형
안녕하세요 :)
지난글에 DP로 푸는 문제를 올렸었는데요! 그래서 DP문제 하나를 더가져와봤습니다
https://programmers.co.kr/learn/courses/30/lessons/43105
문제에서 대각선 방향으로 한칸 오른쪽 또는 왼쪽으로만 이동가능하다고 나와있습니다.
- triangle
[[7],
[3, 8],
[8, 1, 0],
[2, 7, 4, 4],
[4, 5, 2, 6, 5]]
triangle 배열이 이렇게 주어진다면 열이 같거나 또는 열이 하나 큰 쪽으로 이동되록 구현했습니다.
예를 들어서, 지금 값이 2행의 3이라면 8(열이 같음)이나 1(열이 하나 큼)로 이동이 가능하겠죠.
def solution(triangle):
size = len(triangle)
d = [[-1] * size for _ in range(size)]
d[0][0] = triangle[0][0]
for n in range(1, size):
for i in range(len(triangle[n])):
d[n][i] = triangle[n][i] + max(d[n-1][i-1], d[n-1][i])
return max(d[-1])
Author And Source
이 문제에 관하여([Python] 프로그래머스(Lv2) - 정수 삼각형), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다 https://velog.io/@kerri/프로그래머스Lv2-정수-삼각형저자 귀속: 원작자 정보가 원작자 URL에 포함되어 있으며 저작권은 원작자 소유입니다.
우수한 개발자 콘텐츠 발견에 전념 (Collection and Share based on the CC Protocol.)