최대합 찾기

아래 그림은 숫자 삼각형을 보여준다. 맨 꼭대기에서 바닥에 까지 한 층에 하나씩 연결되는 길을 찾아내려 가는데 그 합이 최대가 되는 것을 구하려는 문제이다. 여기서 한 층씩 내려간다는 것은 대각선 방향으로 왼쪽 혹은 대각선 방향으로 오른쪽으로 내려가는 것이다. 아래 그림에서 최대가 되는 합은 얼마인가?

출처 : 정보올림피아드 2008년 초등부 12번문제

정답) 37

문제풀이)