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

hanabanana1 6년 전 0

return 도 다 했는데 왜 시간초과가 나오는지 모르겠습니다..ㅠ

#include<stdio.h>
int arr[1001] = {};
int findNum(int n, int k);
int main(void)
{
	int n, k;
	
	scanf("%d %d", &n, &k);
	int j = 2;
	for (int i = 0; i < n-1; i++)
	{
		arr[i] = j;
		j++;
	}

	int val = findNum(n, k);
	printf("%d\n", val);
	
	return 0;
}
int findNum(int n, int k)
{
	int p = 0, flag = 0;
	int cnt = 0, temp = 0;
	while (cnt != k)
	{
		for (int x = 0; x < n - 1; x++)
		{
			if (flag == 0 && arr[x] >= 2)
			{
				if (arr[x] != 0)
				{
					p = arr[x];
					flag = 1;
				}
			}
		}
		for (int j = 0; j < n - 1; j++)
		{
			
			if (arr[j]!=0 && arr[j]%p == 0)
			{
				cnt++;
				if (cnt == k)
				{
					temp = arr[j];
				}
				
				arr[j] = 0;
			}
			flag = 0;
		}
	}
	return temp;
}

chogahui05 6년 전 0

하나 궁금한 게 있습니다.

혹시 1 ~ 100까지 있다고 치면

2를 지우고, 3은 2의 배수가 아니니까 뛰고, 4 지우고, 5는 2의 배수가 아니니까 뛰고, ...

이런 식으로 처리를 하셨나요??

그렇다고 치면..

7의 배수를 지울 때도

7 지우고, 8은 7의 배수가 아니니까 걍 뛰고, ... 이런 식으로 계속 처리한다는 건가요??

그러면 O(n^2)가 아닐까 싶은데요..

7의 배수다 그러면.. 그냥 한번에 7씩 증가시키면 되지 않을까요?

hanabanana1 6년 전 0

배수를 지우는 방식으로 바꿨는데도 시간초과 뜨네요 ㅠㅠ

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

문제

문제

출처

ICPC

[C] 시간초과...

hanabanana1 6년 전 0

chogahui05 6년 전 0

hanabanana1 6년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말