[C++] 알고스팟/동적계획법 - 삼각형 위의 최대 경로 수 세기

문제 링크

https://algospot.com/judge/problem/read/TRIPATHCNT

algospot.com :: TRIPATHCNT

 

이전의 삼각형 위의 최대 경로 문제에서 연장되는 문제입니다.

이전 문제로 각 위치에서의 최대 경로를 아래 오른쪽과 같이 구할 수 있습니다.

 

 

이렇게 구하고난 경로 값을 이용해서

1. 현재 위치에서 한칸 아래  위치

2. 현재 위치에서 오른쪽 한칸 아래 위치

두 값중 더 큰쪽이 항상 최대 경로가 됩니다.

이 때 두 값이 동일하다면 두 곳 모두 최대 경로가 될 수 있습니다.

 

최대 경로를 찾으면 카운트를 해주고 그 아래 값에 대한 최대 경로를 재귀함수로 구해서 더해주면 됩니다.

 

구현 코드