1932

[1932] 정수 삼각형 - Python

/* 문제 */ 위 그림은 크기가 5인 정수 삼각형의 한 모습이다. 맨 위층 7부터 시작해서 아래에 있는 수 중 하나를 선택하여 아래층으로 내려올 때, 이제까지 선택된 수의 합이 최대가 되는 경로를 구하는 프로그램을 작성하라. 아래층에 있는 수는 현재 층에서 선택된 수의 대각선 왼쪽 또는 대각선 오른쪽에 있는 것 중에서만 선택할 수 있다. 삼각형의 크기는 1 이상 500 이하이다. 삼각형을 이루고 있는 각 수는 모두 정수이며, 범위는 0 이상 9999 이하이다. dp 문제다. 각 칸마다 해당 칸에 도착하는 경로들 중 최댓값을 저장한다. 특정 칸에 도착하는 방법은 최대 두 가지 경우밖에 없다. 위에서 아래로 내려온다고 가정했을 때, 왼쪽 위 (단, 현재 칸이 맨 왼쪽 칸이 아니어야 함) 오른쪽 위 (단, ..