글 읽기 - 시간초과..

leekh2002 4년 전 0

ㅇ왜 시간초과가 나올까요..

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

string cmp(string a, string b)
{
	if (a.size() == 0 || a.size() > b.size())
		return b;
	if (b.size() > a.size())
		return a;
	return min(a, b);
}

int main()
{
	string s, dp[1010];
	char c[9] = "(){}[]";
	int t, i, j,n,k;
	scanf("%d", &t);
	dp[1] = "12";
	dp[2] = "34";
	dp[3] = "56";
	for (i = 0; i < t; i++)
	{
		scanf("%d", &n);
		for (j = 1; j <= n; j++)
		{
			if (j % 2 == 0)
				dp[j] = cmp(dp[j], "1" + dp[j / 2] + "2");
			if (j % 3 == 0)
				dp[j] = cmp(dp[j], "3" + dp[j / 3] + "4");
			if (j % 5 == 0)
				dp[j] = cmp(dp[j], "5" + dp[j / 5] + "6");
			for (k = 1; k < j; k++)
				dp[j] = cmp(dp[j], dp[k] + dp[j - k]);
		}
		
		for (j = 0; j < dp[n].size(); j++)
		{
			printf("%c", c[dp[n][j] - '1']);
		}
		printf("\n");

	}
	return 0;
}

evenharder 4년 전 1

T = 100이고, 이후 100개의 1000이 입력으로 주어지는 상황에서 테스트를 해보시는 게 좋을 것 같습니다. 1초 안에 돌지는 않을 것 같습니다.

dp식은 잘 설계하신 것으로 보입니다. 그럼 한 번 계산한 dp를 매 테스트 케이스마다 다시 계산할 필요가 있을까요?

테스트 케이스에 따라 dp값이 바뀌지 않으므로, 한 번만 조사해도 충분합니다.

leekh2002 4년 전 1

감사합니다! 덕분에 풀었습니다

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

문제

문제

출처

ICPC

시간초과..

leekh2002 4년 전 0

evenharder 4년 전 1

leekh2002 4년 전 1

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말