글 읽기 - 시간초과 어느부분이 문제일까요??

swinnovator 4년 전 0

질문게시판에 있는 답은 다 똑같이 나오는데

시간초과가 자꾸떠요..

어느 부분에서 시간초과가 나는걸까요

#include<iostream>
using namespace std;

int sumFromAtoB(int arr[], int from, int to);

int main() {
	int max = -1000000000;
	int *arr, size;

	cin >> size;
	arr = new int[size];

	for (int i = 0; i < size; i++) cin >> arr[i];

	int idx = 0;
	for (int group = 0; group < size; group++) {
		for (int begin = 0, end = begin + group; end != size; begin++, end++) {
			int temp = sumFromAtoB(arr, begin, end);
			if (max < temp) max = temp;
		}
	} 
	cout << max << endl;

	return 0;
}

int sumFromAtoB(int arr[], int from, int to) {
	int sum = 0;
	for (int idx = from; idx <= to; idx++) sum += arr[idx];
	return sum;
}

shg9411 4년 전 0

저도 잘 못하지만 dp 문제인 만큼 매번 계산하는 것이 아니라 계산했던것을 이용하는 것이 필요할 것 같네요.

숫자들의 합이니까 음수가 되지 않는 한 계속 더하는게 제일 큰 값을 만들 수 있겠죠.

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

문제

문제

출처

ICPC

시간초과 어느부분이 문제일까요??

swinnovator 4년 전 0

shg9411 4년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말