가로 , 세로 크기 격자의 각 칸에 몇 개씩의 마시멜로가 들어 있다. 제일 왼쪽 위 칸에서 제일 오른쪽 아래 칸으로 가면서 지나가는 칸들에서 마시멜로를 모으려고 한다. 단, 이동하는 것은 현재 칸에서 바로 오른쪽 혹은 바로 아래쪽 칸으로만 가능하다.
오른쪽 프로그램을 채워 봅시다.
오른쪽 코드에서 A
에는 입력 값들이 저장되어 있고, B
는 A
와 동일한 크기의 배열인데 B[n][n]
의 값이 최종 답이 될 것이다.
max(P, Q)
함수는 P
와 Q
중 더 큰 값을 리턴하는 함수이다.
프로그램의 입력 첫 줄에는 격자의 크기 이 주어진다. 다음 개의 줄 각각에는 격자의 한 행의 칸들에 있는 마시멜로의 개수가 주어진다.
은 1 이상 1000 이하이다. 각 칸의 마시멜로 개수는 1 이상 100 이하의 정수이다.
프로그램은 모을 수 있는 가장 많은 마시멜로의 개수를 출력한다.
4
1 3 2 1
1 2 1 2
1 1 2 1
3 1 2 1
12