글 읽기 - 가르침 시간초과 도와주세요 ㅠㅠ

scka 7년 전 0

가르침 문제 시간복잡도로는 문제 없는것 같은데 89%에서 자꾸만 시간초과가 납니다 ㅠㅠ

N의 개수를 최대로 넣었을때도 바로 나오는데 왜 그런지 모르겠습니다 ㅠㅠ

#include <stdio.h>
#include <string.h>
#include <map>
#include <algorithm>
using namespace std;
map <char, int>m;
int arr[55];
int dp[1<<21];
int n,k;
int ar[1<<21];
int main()
{
	m['a'] = -1;
	m['c'] = -1;
	m['n'] = -1;
	m['t']= -1;
	m['i']= -1;
	m['b']= 0;
	m['d']= 1;
	m['e']= 2;
	m['f']= 3;
	m['g']= 4;
	m['h']= 5;
	m['j']= 6;
	m['k']= 7;
	m['l']= 8;
	m['m']= 9;
	m['o']= 10;
	m['p']= 11;
	m['q']= 12;
	m['r']= 13;
	m['s']= 14;
	m['u']= 15;
	m['v']= 16;
	m['w']= 17;
	m['x']= 18;
	m['y']= 19;
	m['z']= 20;
	scanf("%d%d",&n,&k);
	char c;
	scanf("%*c");
	for (int i = 0; i < n; i++)
	{
		while (1)
		{
			scanf("%c", &c);
			if (c == '\n' || c == EOF)
			{
				break;
			}
			if(m[c]!=-1)
				arr[i] = arr[i]|(1<<m[c]);
		}
	}
	if (k < 5)
	{
		printf("0\n");
		return 0;
	}
	int ans = 0;
	int sum = 0;
	for(int i = 1;i<(1<<21);i++)
	{
		dp[i] = 987654321;
	}
	dp[0] = 0;
	for(int i = 0;i<21;i++)
	{
		dp[1<<i] = 1;
	}
	int t = 1; 
	for(int i = 3;i<(1<<21);i++)
	{
		dp[i] = min(dp[1<<t]+dp[i - (1<<t)],dp[i]);
		if(i == (1<<t+1))
			t++;
	}
	t = 0;
	for(int i = 0;i<(1<<21);i++)
		if(dp[i] == k-5)
			ar[t++] = i;
	for(int i = 0;i<t;i++)
	{
		sum = 0;
		for(int k = 0;k<n;k++)
		{
			if((arr[k]&ar[i]) == arr[k])
				sum++;
		}
		if(ans<sum)
			ans = sum;
	}
	printf("%d\n",ans);
}

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

문제

문제

출처

ICPC

가르침 시간초과 도와주세요 ㅠㅠ

scka 7년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말