문제
정올 빌딩은 n층이고 각 층은 n개의 구역으로 구성되어있다. 이 건물에 있는 청소로봇은 건물의 입구에서 시작하여 맨 위층의 창고가 있는 방향으로만 청소를 한다.
예를 들어 1층 1구역에서 2구역으로 이동 했으면 1구역으로 돌아가지 않는다. 또 1층에서 2층으로 이동을 했으면 1층으로 돌아가지 않는다. 당연히 2층에서도 1층에서 지나온 1구역에는 가지 않는다. 즉, 층이든 구역이든 오름차순방향으로만 움직인다.
격자 모양의 건물정보에 각 쓰레기의 양이 표시되어있는 지도를 로봇에게 입력하면 로봇은 한 번의 청소로 가장 많은 쓰레기를 치운다.
건물의 입구는 항상 (1, 1)이고 창고의 위치는 항상 (n, n)이다.
위의 경우 가장 많이 치운 쓰레기의 양은 12가된다.
입력
첫줄에 격자의 크기 n(5≤n≤1000)이 주어진다.
두 번째 줄부터 n*n의 크기에 각 쓰레기의 양 m(0≤m≤100)이 공백으로 구분하여 들어온다.
출력
가장 많이 청소한 쓰레기의 양을 출력한다.
예제
5
0 4 0 0 0
0 0 0 3 0
0 2 4 0 0
0 0 0 2 0
0 3 0 0 0
12
출처
pai2
로그인해야 코드를 작성할 수 있어요.