글 읽기 - 시간초과 (자바) dp사용

ssifood 5년 전 0

안녕하세요.

자바로 공부하면서 소스작성했는데요.

시간초과가 뜹니다.

이거 다른분들 것 많이 참고했는데, 다른분들은 그냥 인풋받음녀서 계산했고

이건 다 인풋받고 이것을 재귀했는데요.

어떻게 개선해야 시간초과가 안뜰까요??

저서: 프로그래밍대회에서 배우는 알고리즘 문제해결전략 참고해서 학습중입니다.만.

import java.util.*;
import java.math.*;

// f(x,y) =  now(x, y)  + sum(x-1, y-1)

public class Main {
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int n = sc.nextInt();
		int[][] ad = new int[n][n];
		int[][] cache = new int[n][n];

		for (int i = 0; i < n; i++) {
			for (int j = 0; j < i + 1; j++) {
				ad[i][j] = sc.nextInt();
				cache[i][j] = -1;
			}
		} // for

		// start값.
		int i = 0;
		int j = 0;

		int ret = calc(cache, ad, i, j);
		System.out.println(ret);

	}

	private static int calc(int[][] cache, int[][] ad, int i, int j) {
		// TODO Auto-generated method stub
		// 기저 삼각형 밖의 좌표
		int n = ad.length;
		if (i == n - 1) {
			return ad[i][j];
		}
		int ret = cache[i][j];
		if (ret != -1) {
			return ret;
		}
		cache[i][j] = ret;
		return ret = Math.max(calc(cache, ad, i + 1, j), calc(cache, ad, i + 1, j + 1)) + ad[i][j];

	}
}

indioindio 5년 전 2

cache[i][j] = ret;
return ret = Math.max(calc(cache, ad, i + 1, j), calc(cache, ad, i + 1, j + 1)) + ad[i][j];

여기서 cache의 업데이트가 안되고 있네요.

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

문제

문제

출처

ICPC

시간초과 (자바) dp사용

ssifood 5년 전 0

indioindio 5년 전 2

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말