Submission #2398

#	Time	Username	Problem	Language	Result	Execution time	Memory
2398		alephnull	생일수 I (GA4_birthday1)	C++98	100 / 100	681 ms	5284 KiB

birthday1

#include <iostream>
#include <cstdio>
#include <algorithm>
#define N 1000001
#define INF 987654321
using namespace std;

int main() {
	int *dp=new int [N+10];
	for(int i=0;i<N+10;i++){
		dp[i]=INF;
	}
	dp[0]=0;dp[3]=dp[5]=dp[8]=1;
	for(int i=0;i<N;i++){
		if(dp[i+3]>dp[i]+1)dp[i+3]=dp[i]+1;
		if(dp[i+5]>dp[i]+1)dp[i+5]=dp[i]+1;
		if(dp[i+8]>dp[i]+1)dp[i+8]=dp[i]+1;
	}
	int t;scanf("%d",&t);
	for(int x=0;x<t;x++){
		int n;scanf("%d",&n);
		if(dp[n]==INF)
			printf("%d\n",-1);
		else{
			int a=0,b=0,c=0;
			while(n>0){
				if(dp[n-3]==dp[n]-1){a++;n-=3;}
				else if(dp[n-5]==dp[n]-1){b++;n-=5;}
				else if(dp[n-8]==dp[n]-1){c++;n-=8;}
			}
			for(int i=0;i<a;i++)printf("%d",3);
			for(int i=0;i<b;i++)printf("%d",5);
			for(int i=0;i<c;i++)printf("%d",8);
			printf("\n");
		}
	}
}

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