23.03.07 파이썬 코딩 퀴즈#187 정수 삼각형(프로그래머스 스쿨)

이번 문제는 정수 삼각형 문제이다.

꼭대기에서 바닥까지 이어지는 경로중에 가장 합이 큰 경로의 합으 ㄹ반환해야 한다.

아래로 내려가는 방법은 대각선 방향 한칸 오른쪽 또는 왼쪼으로미나 이동 가능하다.

별다른 조건은 없다.

위 예시 에서는 30이 해당 정수 삼각형의 최대값 루트이다.

정사각형으로 보면 조금 헷갈릴수 있으니 삼각형을 다시 그려보자.

이제 좀 익숙한 모양이 나왔다. 

index를 기준으로 설명하면, 다음 열에서 선택가능한 index는 현재 index, index+1 두가지 이다.

즉 각 열의 index 0 은 윗 열의 index 0 에 의해서만 선택이 가능하고, 반대로 index -1 은 윗 열의 -1 을 선택 했을때에만 선택이 가능하다.

굳이 새로운 배열을 만들지 않고 해당 triangle 에 누적값을 전달해도 문제는 없다.

먼저 dp 라는 2차원 배열을 만들어 주고, [0] 에는 triangle[0][0] 을 넣어주고 시작한다.

이중 반복문을 통해 triangle을 탐색하게 되는데, 이제 위에서 찾은 규칙들을 적용해주면 된다.

먼저 j가 0인 경우라면 바로 윗 열의 index 0 과 합산한 값을 dp 에 전달한다.

j 가 i 와 같다면 마지막 index라는 뜻이므로, 바로 윗 열의 index -1 과 합산한 값을 dp 에 전달한다.

그렇지 않은 경우라면, 두개의 경우의 수중 최대값을 전달하면 된다.