[KOITP] 폐지줍기

출    처 : http://koitp.org/problem/SDS_PRO_6_1/read/

시간 제한	메모리 제한	제출 횟수	정답 횟수 (비율)	정답자 수
1.0 초	512 MB	1292	684 (53%)	584

문제

N×N 격자로 이루어진 도시가 있다. 이 도시 군데군데에는 폐지가 버려져 있다.

범수는 가장 왼쪽 위 격자 (1, 1)에서 출발하여 가장 오른쪽 아래 격자 (N, N)까지 이동하며 폐지를 줍는데, 최단 경로를 따라가야만 한다. 즉, 인접한 오른쪽 칸 또는 아래쪽 칸으로만 이동할 수 있다. 이 때, 범수가 수집할 수 있는 폐지의 최대값을 출력하시오.

출발점과 도착점에 위치한 폐지 또한 주울 수 있다.

입력

첫 번째 줄에는 도시의 크기 N이 주어진다. (2 ≤ N ≤ 200)

두 번째 줄부터 N개의 줄에 걸쳐 도시의 정보가 주어진다. 도시의 정보 중 i번째 줄의 j번째 숫자는 격자 (i, j)에 버려진 폐지의 양 A_ij을 나타낸다. (0 ≤ A_ij ≤ 1000)

출력

범수가 주울 수 있는 최대 폐지 양을 출력한다.

힌트

예제 입력

4
1 0 1 7
2 0 2 0
0 2 2 1
1 3 3 2

예제 출력

13

< Comment >

 폐지줍기는 비교적 쉬운 문제였습니다. DP 정의는 i,j 인덱스까지 이동하였을 경우의 최대 폐지 수집값으로 정의하고 풀었습니다. 올수 있는 위치가 왼쪼과 오른쪽으로 고정되어있으므로 어렵지 않게 풀 수 있었습니다.

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.StringTokenizer;

public class GarbageCollector {
	
	public static int N = 0;
	public static int map[][] = null;
	
	public static int dp[][] = null;

	public static void main(String[] args) throws Exception {
		
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
		
		N = Integer.parseInt(br.readLine());
		map = new int[N][N];
		dp = new int[N][N];
		StringTokenizer st = null;
		for (int i = 0 ; i < N ; i++) {
			
			st = new StringTokenizer(br.readLine());
			for (int j = 0 ; j < N ; j++) {
				map[i][j] = Integer.parseInt(st.nextToken());
			}
		}
		
		int sum = 0;
		for (int i = 0 ; i < N ; i++) {
			sum = sum + map[0][i];
			dp[0][i] = sum;
		}
		sum = 0;
		for (int i = 0 ; i < N ; i++) {
			sum = sum + map[i][0];
			dp[i][0] = sum;
		}
		
		for (int i = 1 ; i < N ; i++) {
			
			for (int j = 1 ; j < N ; j++) {
				dp[i][j] = Math.max(dp[i][j-1], dp[i-1][j]) + map[i][j];
			}
		}
		
		bw.write("" + dp[N-1][N-1]);
		bw.flush();
		bw.close();
	}
}