Submission #2167

#	Time	Username	Problem	Language	Result	Execution time	Memory
2167		jwvg0425	생일수 I (GA4_birthday1)	C++98	100 / 100	748 ms	12604 KiB

birthday1

#include<stdio.h>
int t,n;
int table[1000001],trace[1000001],number[1000001];
int min(int a,int b){return a<b?a:b;}
int main()
{
	int i,m,k=8,j,a;

	scanf("%d",&t);
	trace[3]=trace[6]=3;
	trace[5]=5;
	trace[8]=8;
	table[3]=table[5]=table[8]=1;
	table[6]=2;
	table[1]=table[2]=table[4]=table[7]=100;
	for(a=0;a<t;a++)
	{
		scanf("%d",&n);
		if(n==1||n==2||n==4||n==7)
		{
			printf("-1\n");
			continue;
		}
		if(n>k)
		{
			for(i=k+1;i<=n;i++)
			{
				m=min(table[i-3],table[i-5]);
				m=min(m,table[i-8]);
				table[i]=m+1;
				if(m==table[i-3])trace[i]=3;
				if(m==table[i-5])trace[i]=5;
				if(m==table[i-8])trace[i]=8;
			}
			k=n;
		}
		j=0;
		for(i=n;i>0;)
		{
			number[j++]=trace[i];
			i-=trace[i];
		}
		for(j--;j>=0;j--)printf("%d",number[j]);
		printf("\n");
	}
}

• Subtask 1: 14 / 14
• Subtask 2: 19 / 19
• Subtask 3: 26 / 26
• Subtask 4: 41 / 41