글 읽기 - (C언어) 시간초과를 어떻게 해결할 수 있을까요 ㅠㅠ

anwhrjs815 2년 전 0

a의 b제곱을 c로 나눈 나머지 == (a의 b/2제곱을 c로 나눈 것)을 제곱하여 c로 나눈 나머지 인 것을 이용하였습니다. 시간 문제만 아니면 답은 잘 나오는데 시간이 나꾸 초과가 돼서 틀리는데 어떻게 해야 시간을 줄일 수 있는지 궁금합니다.

#include<stdio.h>
#include<math.h>

int tree (int a, int b, int c) 
{
    int tem;
    if(pow(a,b/2)>c)
    {
        tem=tree(a,b/2,c)*tree(a,b-b/2,c);
    }
    else
    {
        tem=pow(a,b);
    }
    return tem%c;
} 
 
int main () 
{
    int a,b,c;
    
    scanf("%d %d %d",&a,&b,&c);

    printf("%d\n",tree(a,b,c));
    return 0;
}

cwd1 2년 전 0

math.h에 내장되어 있는 pow함수를 쓰면 시간초과가 나서 분할정복을 이용해 직접 구현해야 합니다.

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

문제

문제

출처

ICPC

(C언어) 시간초과를 어떻게 해결할 수 있을까요 ㅠㅠ

anwhrjs815 2년 전 0

cwd1 2년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말