43105

날짜: 2022년 1월 31일 오후 5:51

코드

각 위치별로 이동할 때 나올 수 잇는 최대값을 저장하는 삼각형을 만들었다.

이 삼각형을 만들기위한 점화식은 간단했다.

$a_{x,y}$를 y번 째줄의 x번 째 숫자로 정의를 하면 다음과 같은 점화식이 나온다.

$$ a_{x,y} = max(a_{x-1, y-1}, a_{x, y-1}) $$

삼각형이 완성이 되면 가장 아래줄의 수 중에서 가장 큰 값을 찾으면된다.