글 읽기 - 시간초과 나는 이유를 모르겠어요..

jihea37 7년 전 0

dp사용해서 풀었고,

백준님이 주신 답과 다른점은 저는 재귀를 이용한다는 점 뿐인거 같은데

계속 시간초과가 뜹니다.

Scanner 바꿔봐도 시간초과 뜨는데 Scanner 문제는 아닌거 같아요.

import java.util.Scanner;

class Main {

	static int[][] D;
	static int[][] candy;

	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int n = sc.nextInt();
		int m = sc.nextInt();
		
		D = new int[n+1][m+1];
		candy = new int[n+1][m+1];
		
		for(int i=1; i<=n; i++){
			for(int j=1; j<=m; j++){
				candy[i][j]=sc.nextInt();
			}
		}
		
		System.out.println(dp(n, m));
		
	}
	
	static int max(int a, int b, int c){
		if(a>b){
			if(a>c){
				return a;
			}else{
				return c;
			}
		}else{
			if(b>c){
				return b;
			}else{
				return c;
			}
		}
	}
	
	static int dp(int i, int j){
		if(i==0 || j==0){
			return 0;
		}
		if(i==1 && j==1){
			return candy[1][1];
		}
		if(D[i][j]!=0){
			return D[i][j];
		}
		D[i][j] = max(dp(i-1, j), dp(i, j-1), dp(i-1, j-1))+candy[i][j];
		return D[i][j];
	}
}

sgchoi5 7년 전 0

하향식(재귀)으로 푸신 분 찾아보니 BufferedReader 로 입력 처리하셨네요.

Scanner 쓰면 느려서 안 되나 봐요.

jihea37 7년 전 0

BufferedReader로 바꿔봐도 시간초과 나요...

zlzmsrhak 7년 전 0

dp값이 전부 0인 경우, 테이블에 초기값과 동일한 값이 기록되기 때문에 계속 함수가 호출될 수 있습니다.

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

문제

문제

출처

ICPC

시간초과 나는 이유를 모르겠어요..

jihea37 7년 전 0

sgchoi5 7년 전 0

jihea37 7년 전 0

zlzmsrhak 7년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말