Q11048. 이동하기

아래, 오른쪽 방향으로 가며 상, 좌의 max value를 더하며 나아가는 방식입니다.

문제 조건에는 대각선 방향이동도 존재하지만,

대각선 이동 값 <= 오른쪽, 아래 이동 값 

대각선 이동 값 <= 아래, 오른쪽 이동 값 

이므로, 생략했습니다.

array[x][y] += max(array[y][x-1], array[y-1][x])

import java.io.BufferedReader; import java.io.InputStreamReader; import java.util.StringTokenizer; public class Q11048 { static long[][] array; public static void main(String[] args) throws Exception { BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); StringTokenizer st = new StringTokenizer(br.readLine()); int y = Integer.valueOf(st.nextToken()); int x = Integer.valueOf(st.nextToken()); array = new long[y+1][x+1]; for (int i = 1; i <= y; i++) { st = new StringTokenizer(br.readLine()); for (int j = 1; j <= x; j++) { long value = array[i-1][j]; if (value < array[i][j-1]) { value = array[i][j-1]; } array[i][j] = Integer.valueOf(st.nextToken()) + value; } } System.out.println(array[y][x]); } }