프로그래머스 코딩테스트 - 정수 삼각형(Lv3)
DP table을 만들어 쉽게 풀 수 있는 문제.
- 계산 방법의 경로를 역추적하면 바로 위에서 오거나, 그 옆에서 오거나 두가지 경우임.
- 양 끝에 있는 건 예외처리 고고.
def solution(triangle):
n = len(triangle[-1])
dp = [[-1]*j for j in range(1,n+1)] # 테이블 생성
dp[0]=triangle[0]
# print(dp)
for i in range(n):
if i==0:
continue;
for j in range(i+1):
if j==0:
dp[i][j] = dp[i-1][j] + triangle[i][j]
elif j==i:
dp[i][j] = dp[i-1][j-1] + triangle[i][j]
else:
dp[i][j] = max(dp[i-1][j-1], dp[i-1][j]) + triangle[i][j]
return max(dp[-1])
Author And Source
이 문제에 관하여(프로그래머스 코딩테스트 - 정수 삼각형(Lv3)), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다 https://velog.io/@crosstar1228/프로그래머스-코딩테스트-정수-삼각형Lv3저자 귀속: 원작자 정보가 원작자 URL에 포함되어 있으며 저작권은 원작자 소유입니다.
우수한 개발자 콘텐츠 발견에 전념 (Collection and Share based on the CC Protocol.)