글 읽기 - #2501 - 약수 구하기 (정답은 맞았지만 시간 관련된 외적인 질문)

guardian_demon 7년 전 0

제가 제출한 두 개의 코드가 있습니다.

첫 번째 코드는 직접 올려가면서 나눠보는 방식이고

두 번째 코드는 행렬을 이용해 나눠본 방식인데

두 코드 간의 시간이 크게 차이나는 이유를 아시는 분 계신가요?

감사합니다.

- Guardian_demoN

//#1 - 아래 소스코드는 타임아웃이 걸렸습니다.
#include <stdio.h>

int main(void) {
	int count = 1;
	int tester = 1;
	int a, b;
	scanf("%d %d", &a, &b);
	while(1){
        //while(1)이지만 n, k가 10000 이하라서 괜찮겠지, 싶었지만...
		if(count == b){
            //만약 b가 count와 같으면 루틴을 끝내고 나갑니다.
			break;
		}
		if(a % tester == 0){
				count++;
		}
		tester++;
	}
	printf("%d", tester);
	return 0;
}

//#2 - 아래 소스코드는 맞았습니다. 시간은 0ms.
#include <stdio.h>

int main(void){
	int n;
	int k;
	scanf("%d %d", &n, &k);
	int count = 1;
	int arr[10000];
    //약수가 생길 때마다 arr[10000]에 저장해나가는 방식입니다.
    //물론, 10000개나 되는 약수를 가진 10000 이하의 수는 없겠지만 편의를 위해...
	for(int i = 1;i <= n;i++){
		if(n % i == 0){
			arr[count] = i;
			count++;
		}
	}
	printf("%d", arr[k]);
	return 0;
}

lightseller 7년 전 1

1번 코드의 count 변수는 a가 tester로 나누어 떨어질 때만 증가하네요

그런데 tester 변수가 a보다 커져서 a % tester 가 0이 되지 못하게 되면 while문은 강제종료가 안 되겠지요?

guardian_demon 7년 전 0

으익;;; 초기화를 안했군요...

감사합니다;

-Guardian_demoN

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

문제

문제

출처

ICPC

#2501 - 약수 구하기 (정답은 맞았지만 시간 관련된 외적인 질문)

guardian_demon 7년 전 0

lightseller 7년 전 1

guardian_demon 7년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말