boj-11048

Main.java

/**
 * Created by jojoldu@zuminternet.com on 2016-05-24.
 */

import java.util.Scanner;

/**
 * https://www.acmicpc.net/problem/11048
 */
public class Main {
    private static int[][] maze;
    private static int[][] maxList;
    private static int height;
    private static int width;

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        height = sc.nextInt();
        width = sc.nextInt();
        maze = new int[height+1][width+1];
        maxList = new int[height+1][width+1];

        for(int i=1;i<=height;i++){
            for(int j=1;j<=width;j++){
                maze[i][j] = sc.nextInt();
            }
        }
        System.out.println(move(height,width));

    }

    private static int move(int i, int j){
        if(i == 1 && j == 1){
            return maze[i][j];
        }

        if(i < 1 || j < 1){
            return 0;
        }

        if(maxList[i][j] > 0){
            return maxList[i][j];
        }

        maxList[i][j] = move(i-1, j) + maze[i][j];
        int other = move(i, j-1) + maze[i][j];

        if(maxList[i][j] < other){
            maxList[i][j] = other;
        }

        return maxList[i][j];
    }
}

재귀로 풀었을 경우

• 시간초과로 안됨 망할 ㅋㅋㅋㅋㅋㅋㅋㅋ