글 읽기 - [C++] 시간초과

lucete171 3년 전 0

시간 초과가 나는 이유는 알고 있습니다

arr에 숫자 입력하는데 5만번 정렬시키는데 5만번 이하로 시키면 당연히 시간초과가 나는 건 알겠는 데

입력할 때 정렬을 같이 시킬까요...어떻게 하면 이 방법을 쓰면서 시간 초과가 안 날 수 있을까요?

방법은 이렇습니다

aaaa666 - i=0 - 10000개

aaa666a - i=1 - 10000개

aa666aa - i=2 - 10000개

a666aaa - i=3 - 10000개

666aaaa - i=4 - 10000개

a자리에 숫자를 대입하는 방법을 사용하고 정렬시켜버렸습니다ㅜㅜ

생각해보면 10000번까지니까 굳이 i=4를 안 해도 될 것 같아서 빼긴 했습니다

#include <stdio.h>
#include <math.h>

void swap(int *x,int *y){
	int temp;
	temp=*x;
	*x=*y;
	*y=temp;
}

void select(int arr[],int n){
	int min_index=0;
	for(int i=0;i<(n-1);i++)
	{
		for(int j=(i+1);j<n;j++)
		{
			if(arr[min_index]>arr[j])
			{
				min_index=j;
			}
		}
		if(i!=min_index)
		{
			swap(&arr[min_index],&arr[i]);
		}
	}
}

int main()
{
	int n;
	scanf("%d",&n);
	int arr[40001]={0};
	int t=0;
	for(int i=0;i<4;i++)
	{
		int a=pow(10,i);
		for(int j=0;j<pow(10,4-i);j++)
		{
			for(int k=0;k<pow(10,i);k++)
			{
				arr[t]=a*666+j*pow(10,3+i)+k;
				t++;
			}
		}
	}
	
	select(arr,40000);
    printf("%d",arr[n]);
	return 0;
}

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

문제

문제

출처

ICPC

[C++] 시간초과

lucete171 3년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말