글 읽기 - 똑같은 알고리즘인데 자바에서만 시간초과뜹니다.

kwon5891 2년 전 0

똑같은 로직으로 c++로 짜면 정답이네요.

아마 자바의 재귀 깊이를 따로 조정할 수 없어서 생기는 문제 같습니다.

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;


public class Main {
    public static int[] dp;
    public static int[] p;
    public static int[] t;
    public static int n;
    public static int find(int x){
        if(x > n) return 0;
        if(dp[x] != -1) return dp[x];
        dp[x] = Math.max(find(x + t[x]) + p[x], find(x + 1));
        return dp[x];
    }
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;
        n = Integer.parseInt(br.readLine());
        t = new int[n+1];
        p = new int[n+1];
        dp = new int[n+1];
        for(int i = 1 ; i <=  n ; i ++){
            st = new StringTokenizer(br.readLine());
            t[i] = Integer.parseInt(st.nextToken());
            if(i + t[i] - 1> n) p[i] =0;
            else p[i] = Integer.parseInt(st.nextToken());
            dp[i] = -1;
        }
        dp[n] = p[n];
        if(n == 1){
            System.out.println(p[1]);
            return;
        }

        find(1);
        System.out.println(dp[1]);



    }
}

djm03178 2년 전 0

이 문제에 C++로 제출하신 기록이 없어서 C++로는 어떻게 하셨는지 모르겠지만, 재귀 깊이를 조정하지 못해서 문제가 된다면 런타임 에러가 나지 시간 초과와는 관계가 없습니다.

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

문제

문제

출처

ICPC

똑같은 알고리즘인데 자바에서만 시간초과뜹니다.

kwon5891 2년 전 0

djm03178 2년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말