글 읽기 - 이 방법으로는 왜 시간초과가 나는지 궁금합니다.

kangssun 2년 전 0

최초에 브루트포스 방식으로 구현한 코드입니다.

시간복잡도를 계산했을때 1초를 넘기지 않을거라 생각해서 이렇게 구현하였는데

제출시에 시간초과로 뜨네요 gcd사용해서 문제 해결은 했는데 브루트포스방식으로도 되지 않을까했었기에 질문합니다.

감사합니다.

#include<iostream>
#include<cstring>
#include<cstdio>
#include<cmath>
using namespace std;


int main() {
	long long int A, B;
	long long int max=0, min=0;
	long long int i = 2;
	cin >> A >> B;
	while(1){

		if ((A % i == 0) && (B % i == 0)) min = i;
		if ((i % A == 0) && (i % B == 0)) {
			max = i;
			break;
		}
		i++;
	}
	if (min == 0) min = 1;
	cout << min << "\n" << max << "\n";
	
}

jeha0714 2년 전 0

최소공배수는 A와 B 중 큰수를 기준으로 1씩 키워가면서 찾으시고

최대공약수는 A와 B 중 작은수를 기준으로 1씩 감소해가시면서 찾아보시길 바랍니다.

작성자님 코드를 위와 같이 조언드린것처럼 살짝 변형하여 제출하니 시간초과없이 완료됩니다 :)

jeha0714 2년 전 0

위를 보시고도 해결이 안되신다면 아래 코드를 참고하시길 바랍니다~

-------------------------------------------------------------------------------------------

#include<iostream>
#include<cstring>
#include<cstdio>
#include<cmath>
using namespace std;


int main() {
	long long int A, B;
	long long int max=0, min=0;
	cin >> A >> B;
	long long int i = A > B ? A : B;
	long long int j = A < B ? A : B;
	while(1){ //최소공배수

		if ((i % A == 0) && (i % B == 0)) {
			max = i;
			break;
		}
		i++;
	}
	while(1) {//최대공약수
	    if ((A % j == 0) && (B % j == 0)) {
	        min = j;
	        break;
	    }
	    j--;
	    
	}
	
	if (min == 0) min = 1;
	cout << min << "\n" << max << "\n";
	
}

kangssun 2년 전 0

처음 말해주신대로하니 문제없이 통과되네요 제가 시간복잡도를 잘못 계산했었나 봅니다...

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

문제

문제

출처

ICPC

이 방법으로는 왜 시간초과가 나는지 궁금합니다.

kangssun 2년 전 0

jeha0714 2년 전 0

jeha0714 2년 전 0

kangssun 2년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말