#173

마시멜로우

실행 시간 제한2
메모리 제한512MiB
아직 제출한 코드나 실행한 테스트가 없습니다.

가로 , 세로 크기 격자의 각 칸에 몇 개씩의 마시멜로가 들어 있다. 제일 왼쪽 위 칸에서 제일 오른쪽 아래 칸으로 가면서 지나가는 칸들에서 마시멜로를 모으려고 한다. 단, 이동하는 것은 현재 칸에서 바로 오른쪽 혹은 바로 아래쪽 칸으로만 가능하다.

마시멜로우 이동 그림

오른쪽 프로그램을 채워 봅시다.

오른쪽 코드에서 A에는 입력 값들이 저장되어 있고, BA와 동일한 크기의 배열인데 B[n][n]의 값이 최종 답이 될 것이다.

참고 사항

max(P, Q) 함수는 PQ 중 더 큰 값을 리턴하는 함수이다.

입력 형식

프로그램의 입력 첫 줄에는 격자의 크기 이 주어진다. 다음 개의 줄 각각에는 격자의 한 행의 칸들에 있는 마시멜로의 개수가 주어진다.

은 1 이상 1000 이하이다. 각 칸의 마시멜로 개수는 1 이상 100 이하의 정수이다.

프로그램은 모을 수 있는 가장 많은 마시멜로의 개수를 출력한다.

예제

입력

4
1 3 2 1
1 2 1 2
1 1 2 1
3 1 2 1

출력

12
for (j=0; j<=n; j++) B[0][j] = 0; for (i=0; i<=n; i++) B[i][0] = 0; for (i=1; i<=n; i++) { for (j=1; j<=n; j++) { B[i][j] = () + A[i][j]; } } int answer = B[n][n];
cpp
코드를 작성하려면 로그인해 주세요.