정보올림피아드 초등 - 지역예선] 2008년도 13번문제

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

					7
				3		8
			8		1		4
		2		6		5		4
	3		6		2		7		1
7		7		6		5		5		7

①35

②36

③37

④38

⑤39

 

풀이) 가장 아래 노드 부터 거꾸로 찾아 간다.

아래 그림과 같이 다섯번째 노드에서는 (7,3),(7,6),(6,2),(5,7),(7,1)

네번째 노드에서는 (7,6,2),(7,6,6),(5,7,5),(5,7,4)

세번째 노드에서는 (7,6,6,8),(7,6,6,1),(5,7,5,4)

두번째 노드에서는 (7,6,6,8,3),(5,7,5,4,8)

첫번째 노드에서는 (7,6,6,8,3,7)

따라서 정답은 37

 

정답) 3