글 읽기 - 시간복잡도 상으로는 되는거 같은데 왜 초과인지 모르겠습니다.

sotter1020 5년 전 1

이분법으로 계산하였고,

log N에 1000000000이여도, 충분히 돌아갈거라고 생각합니다.

어디서 문제인걸까요?

if(X2 - Z == 1)에서 오래걸리는 걸까요?

1000000000 1

1000000000 500000000

1000000000 98000000

이렇게 해봤는데 바로바로 답이 잘나옵니다.

어딘가에서 무한루프가 되는 걸까요?

#include<iostream>
using namespace std;
long long X, Y;
int main() {
	cin >> X >> Y;
	int Z = Y * 100 / X;
	if (Z >= 99) {
		cout << -1 << endl;
		return 0;
	}
	long long right = X;
	int X2;
	while (true) {
		X2 = (Y + right) * 100 / (X + right);
		if (X2 - Z == 0) break;
		if (X2 - Z > 1)
			right = right / 2;
		else if(X2 - Z == 1)
			right--;
	}
	cout << ++right << endl;
	return 0;
}

sotter1020 5년 전 0

if(X2 - Z == 1)에서 시간이 오래 걸리는거 맞네요! 그 부분 수정해서 풀었습니다.

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

문제

문제

출처

ICPC

시간복잡도 상으로는 되는거 같은데 왜 초과인지 모르겠습니다.

sotter1020 5년 전 1

sotter1020 5년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말