글 읽기 - 고수님들 시간초과 질문드립니다ㅠㅠ

eotlr720 7년 전 0

eclipse로 돌려보면 분명 답은 맞는것 같은데 제출하면 시간초과가 뜨네요ㅠㅠ

뭔가 더 효율적인 방법이 있을까 계속 고민해봤는데도 정말 답이 나오지 않아서 질문드립니다

어떻게 하면 시간초과를 없앨수 있을까요?

import java.util.*;
public class Main{
    public static void main(String[] args){
        Vector<Integer> v = new Vector<Integer>();//n일의 알바비 정보를 담는 벡터
        Scanner scan = new Scanner(System.in);
        int n = scan.nextInt();//총 n일 사이에
        int m = scan.nextInt();//연속된 m일을 일한다
        int max = 0;//출력할 최대값
        int sum = 0;//비교할 합계

        for (int i=0;i<n;i++){
        	int a = scan.nextInt();
        	v.add(a);
        }
        for (int i=0;i<n-m+1;i++){
        	for (int j=0;j<m;j++){
        		sum += v.get(i+j);
        	}//비교를 하기 위해 sum에 연속된 m일의 값을 차례로 더함
        	if (max<=sum){
        		max = sum;
        	}//비교를 하여 최댓값 채택
        	sum = 0;//한번 할때마다 비교값 초기화
        }
        System.out.println(max);
        scan.close();
    }
}

sksdong1 7년 전 2

다이나믹 프로그래밍으로 푸시면 됩니다.

힌트를 드리면

m일을 일할 때 가장 많은 이익을 얻어야 하므로, 무조건 m일을 일해야 됩니다. (음수가 없기 때문에 1~m-1일 사이에서는 최대가 나올 수 없죠)

따라서 1~m일 일한 값을 기준으로, m+1일을 더하고 1일 째를 빼고, m+2일을 더하고 2일 째를 빼면서 최대값을 비교하시면

O(n)에 해결 가능합니다.

eotlr720 7년 전 0

감사합니다! 한번 해볼게요!!

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

문제

문제

출처

ICPC

고수님들 시간초과 질문드립니다ㅠㅠ

eotlr720 7년 전 0

sksdong1 7년 전 2

eotlr720 7년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말