글 읽기 - 고수님들 가르침 부탁드립니다

ekslffh 2년 전 0

예제에 문제들은 적용이 되는데

시간초과가 뜹니다. 어디부분에서 문제인지 알려주실분 계시나요 ㅠㅠ

또한 전체적인 코딩구성에 있어서 문제가 있다고 생각이 드시면 가감없이 말씀해주세요 부탁드립니다 ㅠㅠ

#include <iostream>
using namespace std;

bool compare(int *h,int* temp,int N)
{
	int a = 1;
	for (int i = 0; i < N; i++)
	{
		if (h[i] != -1 && h[i] != temp[i])
			a = 0;
	}
	if (a == 1)
	{
		return true;
	}
	else
		return false;
}

int highested(int N, int* h)
{
	int high = h[0];
	for (int i = 1; i < N; i++)
	{
		if (high < h[i])
			high = h[i];
	}
	return high;
}

void construct(int first,int last,int* temp,int* h,int &answer)
{
	static int a;
	static int N = last - first + 1;
	static int high=highested(N, h);

	for (int i = first; i <= last - 2; i++)
	{
		for (int j = i + 2; j <= last; j++)
		{
			a = 0;
			for (int k = i + 1; k < j; k++)
			{
				a++;
				temp[k]++;
			}
			if (compare(h, temp, N))
				answer++;
			if (a >= 3 && highested(N,temp) <= high)
			{
				construct(i + 1, j - 1, temp, h, answer);
			}
			for (int k = i + 1; k < j; k++)
			{
				temp[k]--;
			}
		}
	}
}

int main()
{
	int N;
	cin >> N;
	int* h = new int[N];
	for (int i = 0; i < N; i++)
		cin >> h[i];
	int* temp = new int[N] {0};//임시저장
	int answer = 0;//정답
	construct(0, N - 1, temp,h,answer);
	if (highested(N, h) == -1)
		cout << answer + 1;
	else
		cout << answer;
}

moon960323 2년 전 1

이 문제의 N제한은 1만으로 단순한 반복문으로 문제를 접근하시면 시간초과를 받게 됩니다.

for i : O(N)

for j : O(N)

compare(..) : O(N)

이렇게만 해도 벌써 O(N^3)으로 N 이 큰 예제에서는 시간초과가 날 수 밖에 없습니다.

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

문제

문제

출처

ICPC

고수님들 가르침 부탁드립니다

ekslffh 2년 전 0

moon960323 2년 전 1

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말