글 읽기 - 왜 시간초과일까요....도와주세요 ㅠㅠ

xowns9418 7년 전 0

문제를풀기위해 N을 제외한 N의 약수중 최대값을 찾는 것이 문제의 답을 찾는 것이라 생각하였습니다.

일반적으로 N을 제외한 N의 약수중 최대값은 N/2부터 1씩 감소시키면서 검사해주면 될거라 생각하였습니다.

그런데 소수의경우는 1이므로 N이 소수인 경우와 소수가 아닌 경우를 나누어 생각하였습니다. 문제의 N최대범위인 10^9을 넣어도 바로 출력이되는데 왜 시간초과가 나는걸까요??

#include<iostream>
using namespace std;

bool isprime(int n) {
	if (n == 1)
		return false;
	else {
		for (int i = 2; i*i <= n; i++) {
			if (n%i == 0) {
				return false;
			}
		}
	}
	return true;
}

int main(void) {
	ios::sync_with_stdio(false);
	int N;
	cin >> N;

	if (isprime(N)) { //소수 일 경우
		cout << N - 1 << '\n';
	}

	else {
		for (int i = N / 2; 0 < i; i--) {//소수가 아닐 경우 N/2부터 1씩 감소시키면서 탐색
			if (N%i == 0) {
				cout << N - i << '\n';
				break;
			}
		}
	}

	return 0;
}

xowns9418 7년 전 0

해결햇습니다 감사합니다!!

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

문제

문제

출처

ICPC

왜 시간초과일까요....도와주세요 ㅠㅠ

xowns9418 7년 전 0

xowns9418 7년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말