글 읽기 - 쉬운 문제 질문입니당...시간초과문제 해결 부탁드려요

dmsgh7678 8년 전 0

계속 시간 초과가 나네요 ㅠㅠ

어떻게 알고리즘을 바꿔야 에러가 안날까요???

도저히 이거 말고는 다른 알고리즘은 생각이 안나서...

도와주세요 ㅠㅜ

#include <stdio.h>
#include <stdlib.h>
int binary(int a,int b)
{
	int i,k=2;
	int temp;
	int count=0;
	if(a>=b)
		temp=b;
	else
		temp=a;
	for(i=0;;i++)
	{
		if(k>temp)
		{
			k=k/2;
			break;
		}
		else
		{
			count++;
			k=k*2;
		}		
	}
	for(i=0;;i++)
	{
		if(temp%k==0)
		{
			break;
		}
		else
		{
			k=k/2;
			count--;
		}
		
	}
	return count;
}



int main(void)
{
	int t;
	int n,a,b;
	int *num;
	int i,k=1;
	scanf("%d",&t);
	num=(int*)malloc(sizeof(int)*t);
	for(i=0;i<t;i++)
	{
		scanf("%d %d %d",&n,&a,&b);
		num[i]=n-binary(a,b);
	}

	for(i=0;i<t;i++)
	{
		printf("%d\n",num[i]);
	}
	


}

ntopia 8년 전 0

n <= 62 라서 2의 n승이 int범위를 넘어갑니다

그러니 a, b 도 int 범위를 넘어갈 수 있고

따라서 입력받을 때 부터 overflow가 날 수 있고

binary함수 안에서도 overflow가 나서 무한루프를 도는 것 같네요

long long 타입은 2^63 - 1 까지 표현할 수 있으니 이걸 사용해보세요

대신 scanf 와 printf 에서 %d 대신 %lld 을 사용해야 합니다

dmsgh7678 8년 전 0

감사합니당!

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

문제

문제

출처

ICPC

쉬운 문제 질문입니당...시간초과문제 해결 부탁드려요

dmsgh7678 8년 전 0

ntopia 8년 전 0

dmsgh7678 8년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말