글 읽기 - 어디서 틀린건가요 ㅠㅠ

robin1001 7년 전 0

마지막 예제가 제대로 작동을 하지 않는데 왜 그런지 모르겠습니다 ㅠㅠ

#include <stdio.h>

bool check(int a){
	while(a){
		if(a%10==3|a%10==6|a%10==9){
			return true;
		}a = a/10;
	}
	return false;
}

int main(){
	int a,b,i; int cnt =0;
	scanf("%d %d", &a,&b);
	for(i=a; i<=b; i++){
		if(i%3==0)cnt++;
		else if(check(i))cnt++;
	}
	printf("%d", cnt%20150523);
	return 0;
}

도 제대로 작동은 하긴 할텐데요? 하지만 a~b까지 수를 하나씩 다 검사하는 방법을 쓰셨는데 [a,b] 범위가 조금만 더 커지면 금방 시간초과가 날겁니다. 그리고 a,b 가 최대 10^100000 이기 때문에 정수형 데이터 타입에 저장할수도 없는 크기입니다. 따라서 범위안에 (3,6,9) 가 포함되어있는 수, 그리고 (3,6,9) 가 포함되어있지 않지만 3의 배수인 수의 개수를 효율적으로 구하는 방법을 찾아야합니다. 조금 더 생각해보시고 막힌 것 같으면 이 editorial을 참고해보세요! 링크

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

문제

문제

출처

ICPC

어디서 틀린건가요 ㅠㅠ

robin1001 7년 전 0

iljimae 7년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말