Q11048. 이동하기

코딩/백준 알고리즘

금손형아 2019. 2. 12. 22:37

아래, 오른쪽 방향으로 가며 상, 좌의 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]);

}