글 읽기 - C++ 시간초과

suengwone 2년 전 0

유클리드 호제법을 이용하여 풀어봤는데 시간초과가 나옵니다.

테스트 케이스는 잘 돌아가는데 어느 부분이 문제인지 잘 모르겠습니다.

뭐가 문제인지 알려주시면 감사하겠습니다.

#include <bits/stdc++.h>

using namespace std;

int Max(int a, int b) {
	if (a > b) {
		return a % b == 0 ? b : Max(a%b, b);
	}
	else if (a < b) {
		return b % a == 0 ? a : Max(b%a, a);
	}
	else {
		return a;
	}
}



int main() {
	int N;
	scanf("%d", &N);
	vector<pair<int,int>> arr;
	for(int i=0;i<N;i++) {
		int a, b;
		scanf("%d%d", &a, &b);
		if (a>b && !a%b) {
			continue;
		}
		else if (a < b && !b%a) {
			a = 1;
			b /= a;
		}
		arr.push_back(pair<int, int>(a, b));
	}

	int a = arr[0].second;
	
	for (int i = 1; i < arr.size(); i++) {
		int b = arr[i].second;
		a = a * b / Max(a, b);
	}

	N==1 ? printf("%d %d\n",1,arr[0].second) : printf("%d %d\n", 1, a);

	return 0;
}

kimhw0820 7달 전 0

max 함수를 고쳐보는게 어떤가요? 반복문으로 함수를 소환하는 과정에서 시간이 많이 걸리니 반복문으로

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

문제

문제

출처

ICPC

C++ 시간초과

suengwone 2년 전 0

kimhw0820 7달 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말