글 읽기 - 2228 시간초과 질문이 있습니다.

lalalalz 4년 전 0

문제 요약 : 크기가 N인 배열에 m개의 구간을 만들었을 때 얻을 수 있는 최대값을 구하라. (단, 구간은 연속되어야 하고, 구간들은 서로 인접하거나 겹처서는 안된다.)

문제 해결 : func( idx, m ) : 배열을 idx 부터 N까지 이용하여 m개의 부분 구간을 만들 수 있을 때 얻을 수 있는 최대값.

정의된 func를 이용하여 재귀적으로 문제를 해결하도록 한다. 이때, DP를 적용시킨다.

질문 :

1. A번째 주석 부분만 있어도 문제가 해결될 수 있다고 생각하는데 B번째 주석 부분이 없으면 시간 초과를 발생시킵니다. 이유가 궁급합니다.

2. A번째 주석 부분의 값은 한번도 캐싱되지 않은 것을 의미하는 즉, 캐싱으로 가질 수 없는 값을 설정하면 된다고 생각합니다. 그런데 캐싱될 수 없는 값인 -987654321로 설정해도 문제가 해결되지 않습니다. 이유가 궁금합니다.

#include <iostream>
#include <algorithm>
using namespace std;

// A 주석 const int MIN = -1987654321;

int N, M;
int pSum[101];
int cache[103][60];

int func(int idx, int m)
{
	int& ret = cache[idx][m];

	if(ret != MIN)        return ret;
	if(m   ==   0)    	  return 0;
	if(idx >    N)	      return MIN;

	// B 주석 ret = -1000000007; 이 부분의 주석 결과가 시간 초과를 발생시킴.

    // 현재 idx에서 구간을 시작하지 않는다.
	ret = max(ret, func(idx + 1, m));
	for(int i = idx; i <= N; ++i)
	{
        // idx ~ i 까지 구간을 만든 뒤, 재귀적으로 문제를 해결한다.
        // 이때, 구간의 합을 부분합을 이용하여 구한다.
		ret = max(ret, func(i + 2, m - 1) + (pSum[i] - pSum[idx - 1]));
	}

	return ret;
}

int main()
{
	cin >> N >> M;

	for(int i = 1; i <= N; ++i)
	{
        // 구간합을 구한다.
		cin >> pSum[i];
		pSum[i] += pSum[i - 1];
	}

	for(int i = 0; i < 103; ++i)
	{
		for(int j = 0; j < 60; ++j)
		{
			cache[i][j] = MIN;
		}
	}

	cout << func(1, M);
}

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

문제

문제

출처

ICPC

2228 시간초과 질문이 있습니다.

lalalalz 4년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말