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

 

[ 문제 ]

[ 문제 설명 ]

위와 같은 삼각형의 꼭대기에서 바닥까지 이어지는 경로 중, 거쳐간 숫자의 합이 가장 큰 경우를 찾아보려고 합니다. 아래 칸으로 이동할 때는 대각선 방향으로 한 칸 오른쪽 또는 왼쪽으로만 이동 가능합니다. 예를 들어 3에서는 그 아래칸의 8 또는 1로만 이동이 가능합니다.

삼각형의 정보가 담긴 배열 triangle이 매개변수로 주어질 때, 거쳐간 숫자의 최댓값을 return 하도록 solution 함수를 완성하세요.

 

[ 문제 풀이 ]

우선 다이나믹 프로그래밍(DP)라는 주제를 보고 들어왔기 때문에 해당 풀이방법을 사용할려고 생각했다. 물론 그걸 안봤어도 했을것 같다.

DP문제는 기본적으로 dp 테이블과 이 테이블이 이전의 값들에 의해 최적의 값으로 채워나가는 메커니즘을 가진다.

문제에서는 위에서 내려와 최대값이 나온다고 했다. 

하지만 딱보면 알겠지만 그렇다면 3번째 줄에서 0에서 4로 갈때 두가지 경우가 있지만 결정하지 못한다. 이는 한번으로 안된다는 뜻이다.

만약에 밑에서 부터 하면 ?? -> Bottom up 으로 해결이 가능하다. 

직접 펜으로 계산해보면 단번에 나오는 것을 알수가 있다. 

 

 따라서 내 풀이는 아래와 같다.

밑에 층부터 위층으로 max값을 쓸면서 올라간다. 별도의 테이블을 만들지 않아도 가능하다.