728x90
반응형
문제 출처: https://school.programmers.co.kr/learn/courses/30/lessons/43105
프로그래머스
코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요.
programmers.co.kr
문제 풀이:
def solution(triangle):
dp = [[0]*len(triangle) for i in range(len(triangle))]
dp[0][0] = triangle[0][0]
for i in range(0, len(triangle)-1):
for j in range(len(triangle[i])):
dp[i+1][j] = max(dp[i+1][j], dp[i][j] + triangle[i+1][j])
dp[i+1][j+1] = max(dp[i+1][j+1], dp[i][j]+triangle[i+1][j+1])
return max(dp[-1])
dp = [[0]*len(triangle) for i in range(len(triangle))]
dp[0][0] = triangle[0][0]
0으로 채워진 dp 만들어주고 맨 위값 넣어준다.
for i in range(0, len(triangle)-1):
for j in range(len(triangle[i])):
dp[i+1][j] = max(dp[i+1][j], dp[i][j] + triangle[i+1][j])
dp[i+1][j+1] = max(dp[i+1][j+1], dp[i][j]+triangle[i+1][j+1])
return max(dp[-1])
마지막 열의 max값 출력
반응형
댓글