글 읽기 - 40%쯤에 시간초과 나옵니다 도와주세요

nodays 2년 전 0

for문으로 작성하면 시간안에 들어가지만,

재귀적으로 구현하니 40%쯤에 시간초과 나옵니다

어떻게 구현해야 재귀적으로 시간안에 들어갈 수 있나요?

package BOJ.DP;

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.StringTokenizer;
import java.util.function.Function;

public class BOJ_15486 {
    private static class Work{
        int day;
        int pay;

        public Work(int day, int pay) {
            this.day = day;
            this.pay = pay;
        }
    }
    public static void main(String[] args) throws Exception{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine()," ");
        Function<String,Integer> stoi = Integer::parseInt;
        int n = stoi.apply(st.nextToken());
        Work input[] = new Work[n];
        for(int i = 0 ; i < n ; i++){
            st = new StringTokenizer(br.readLine()," ");
            int day = stoi.apply(st.nextToken());
            int pay = stoi.apply(st.nextToken());
            input[i] = new Work(day,pay);
        }
        int dp[] = new int[n+1];
//        int max = 0;
//        for(int i = 0 ; i < n ; i++){
//            Work work = input[i];
//            max = Math.max(max,dp[i]);
//            dp[i] = max;
//            if(work.day + i  <= n){
//                dp[work.day + i] = Math.max(dp[work.day + i], max + work.pay);
//            }
//            System.out.println(Arrays.toString(dp));
//        }
        Arrays.fill(dp,-1);
        System.out.println(dfs(n,input,0,dp));
//        int result = Math.max(dp[n-1],dp[n]);
//        System.out.println(result);
    }

    private static int dfs(int n, Work[] input ,int now, int[] dp) {
        if(now >= n){
            return 0;
        }
        if(dp[now] != -1){
            return dp[now];
        }
//        System.out.println(now);
        Work work = input[now];
        int result = 0;
        int next = work.day + now;
        if(next <= n){
            result = Math.max(dfs(n,input,next,dp) + work.pay,dfs(n,input,now + 1,dp));
        }else{
            result = dfs(n,input,now + 1,dp);
        }
        dp[now] = result;
        return result;
    }
}

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

문제

문제

출처

ICPC

40%쯤에 시간초과 나옵니다 도와주세요

nodays 2년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말