Informatica Online Judge

  기숙사와 파닭 [0145 / 0091]

Time Limit(Test case) : 1000(ms)
Number of users who solved : 249   Total Tried : 321


The Champion of this Problem (C++) : gs140742 - 0ms / 440byte
My Best Submission (C++) : N/A

[]

Background

GSHS에서는 파닭을 먹지않고는 GSHS학생이라고 할 수 없을 정도로 유명하다.

그런데 중요한 것은 이 파닭을 배달시켜 먹을 때는 여러가지 위험을 감수해야 한다. 잘못하면 벌점 누적으로 퇴사를 당할 수 있기 때문이다.

문제는 n*n행렬로 구성된 기숙사맵을 분석하여, 가장 안전하게 파닭을 배달시킬 수 있는 경로를 찾는 것이다. 이 때의 안전도를 찾는 것이다.

다음은 n=4인 맵의 예이다. 출발점은 1,1이고 도착점은 n,n(파닭이 배달되는 지점)이다.

각 영역의 값은 위험한 정도를 나타내는 것으로 수가 적을 수록 위험하다. 즉 음수위치의 값들이 더 위험하다.

그리고 이동할 수 있는 경로는 down(아래쪽), right(오른쪽)으로만 가능하다.

8 0 -3 2
-10 7 -9 5
3 4 0 0
2 4 -5 8

조건을 만족시키면서 갈 수 있는 가장 안전한 경로는 (1,1) - (1,2) - (2,2) - (3,2) - (3,3) - (3,4) - (4,4)로 가는 경로이며, 이 때의 안전도는 8 + 0 + 7 + 4 + 0 + 0 + 8 = 27이다.

Input

첫 줄에 한 정수 n이 주어지고, 둘째 줄부터 n+1번째 줄까지 각 n개의 정수가 공백으로 구분되어 입력된다.
(단, 2 <= n <= 1,000 , 각 원소의 크기는 -1000 ~ 1000의 값이다..)

Output

가장 안전한 경로의 위험도의 합을 출력한다.

IO Example

입력
4
8 0 -3 2
-10 7 -9 5
3 4 0 0
2 4 -5 8

출력
27

Submit : [C/C++] | [C++11] | [Obj-C] | [Java] | [Python]
Prob Analysis : [Problem Statistics] | [Solution]