글 읽기 - 시간초과가 나는데 방법을 모르겠네요

jjh4698 8년 전 0

출력은 맞게 나오는거 같은데요

시간초과가 나서요

예를들어 8 11 이 입력되면

처음에는 나누는수 k =2로 잡아서

a , b 가 5 22로 변하고

그다음부터 while문으로 k의 최대 수를 구하기 위해서 k를 증감시키면서

5/22에 가장 근접한 1/k를 구하는데요

이 k 증감 부분을 줄여야 할거 같은데

생각이 떠오르질않네요...

#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>

int main()
{
	
	
	int t_case;
	int a, b;
	double a_b;
	int t_a, t_b;
	double t_a_b;
	int k=2;
	scanf("%d", &t_case);
	while (t_case--)
	{
		scanf("%d%d", &a, &b);
		t_a = a;
		t_b = b;

		while (t_a != 1){
			t_a_b = (double)t_a / t_b;
			
			while(t_a_b < (double)1 / k)
			{
				k++;
			}
			t_a = k*t_a - t_b;
			t_b = t_b*k;
			
		}
		printf("%d\n", t_b);
	}
	
}

lsc4719 8년 전 0

k의 증감부분을 O(1)으로 줄이는 방법이 있었던 것 같네요.

뭔가 부등식을 세우면 됬었던 것 같은..

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

문제

문제

출처

ICPC

시간초과가 나는데 방법을 모르겠네요

jjh4698 8년 전 0

lsc4719 8년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말