[프로그래머스] 정수 삼각형 - 파이썬 python

코딩테스트 - 동적계획법(Dynamic Programming) - 정수 삼각형 [Level3]

문제링크 :정수 삼각형

코딩테스트 연습 - 정수 삼각형

 

문제풀이

다이나믹프로그래밍(DP) 문제입니다.

 

삼각형을 거꾸로 거슬러 올라간다고 생각하면 편합니다.

 

끝에서부터 시작을 해서

자신과 옆에 있는 숫자를 위에 있는 숫자와 더했을 때 더 큰 값을 위에 할당시켜줍니다.

 

할당이 끝나면 삼각형의 가장 밑줄을 없애고 반복합니다.

 

삼각형 원소가 1개가 남으면 자연스레 최댓값이 남게 됩니다.

 

[Python] 정수 삼각형

 

가장 인기 많은 답변

[Most Liked Code] 정수 삼각형

• 코드는 간단하지만 막상 봤을때는 많이 난해하다고 느껴졌습니다.
• 분석하기도 힘듬 ㅠ PASS!!!

 

[Another Code] 정수 삼각형

• 가장 인기있는 코드가 좀 그래서 평범(?)한걸로 가져왔습니다.
• 제 코드가 거꾸로 올라갔다면 이거는 내려가는 방식입니다.
  • 내려가는 방식에서 복잡해지는 부분이 있다면 처음과 끝을 구분하고 중간 부분에서 Max값을 비교해야된다는 점입니다.
  • 오히려 거꾸로 올라가는게 case를 나눌 필요가 없어서 더 편합니다.