글 읽기 - 11048 이동하기

lsh4580 6년 전 0

안녕하세요. 11048번 이동하기 풀면서

계산한 결과를 저장해 놓는 Memoization까지 했는데도

Java에서 시간 초과가 뜨네요;; 왜 그런건지 잘 몰라서 질문 올립니다.

도와주세요~ ㅠㅠ

import java.util.Scanner;

public class Main {
		static int[][] arr;
		static int[][] memo;
	public static void main(String[] args) {
		int m, n;
		Scanner scan = new Scanner(System.in);      // 문자 입력을 인자로 Scanner 생성
		m = scan.nextInt();
		n = scan.nextInt();
		arr = new int[m][n];
		memo = new int[m][n];
		
		for(int i = 0; i < m; i++){
			for(int j = 0; j < n; j++){
				arr[i][j] = scan.nextInt();
			}
		}
		System.out.println(MaxCandyCount(m - 1, n - 1));
	}
	
	static int MaxCandyCount(int m, int n){
		if(memo[m][n] > 0){
			return memo[m][n];
		}
		else if(m == 0 && n == 0){
			return arr[m][n];
		}
		else if(m == 0){
			memo[m][n] =  arr[m][n] + MaxCandyCount(m, n - 1);
			return memo[m][n];
		}
		else if(n == 0){
			memo[m][n] = arr[m][n] + MaxCandyCount(m - 1, n);
			return memo[m][n];
		}
		else{
			memo[m][n] =  arr[m][n] + Max(Max(MaxCandyCount(m - 1, n), MaxCandyCount(m, n - 1)), MaxCandyCount(m - 1, n - 1));
			return memo[m][n];
		}
	}
	
	static int Max(int n1, int n2){
		return n1 > n2 ? n1 : n2;
	}
}

djm03178 6년 전 0

Scanner가 너무 느려서 그럴 수도 있습니다. BufferedReader를 사용해 보세요.

lsh4580 6년 전 0

감사합니다.!!

댓글을 작성하려면 로그인해야 합니다.

문제

문제

출처

ICPC

11048 이동하기

lsh4580 6년 전 0

djm03178 6년 전 0

lsh4580 6년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말