글 읽기 - 시간초과로 틀렸다는데 혹시 어떻게 수정하면 시간초과가 아닐까요?

ruddks1001 4년 전 0

1.혹시 코드가 틀린건지 정말 시간초과인지 알려주실 수 있나요?!

2.시간복잡도계산 for문은 O(N)인거는 아는데 재귀함수면 어떻게 게산하죠?

#include <stdio.h>

int input(void);
int calc(int);
int D[100001]={0,};
int main() {
    int num,sqnum;
    num = input();
    sqnum=calc(num);
    printf("%d",sqnum);
    return 0;
}

int input(){
    int num;
    scanf("%d",&num);
    return num;
}

int calc(int num){
    int *d;
    int tmp;
    d=D;
    for(int i=1; i <= num ;i++){
        if(num==i*i){
            d[num]=1;
            return d[num];
        }
        else if(num > i*i){
            tmp = 1 + calc(num - i*i);
            if(d[num]==0||d[num]>tmp) d[num]=tmp;
        }
        else if(num < i*i){
            break;
        }
    }
    return d[num];
}

djm03178 4년 전 0

1번만 간단히 알려드리겠습니다. 채점 프로그램은 시간 초과일 때만 시간 초과라고 말합니다. 그리고 시간 초과는 프로그램이 무슨 답을 출력했는지는 아예 신경쓰지 않고 강제종료한 것이므로 답이 맞는지 틀리는지는 알 수 없습니다.

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

문제

문제

출처

ICPC

시간초과로 틀렸다는데 혹시 어떻게 수정하면 시간초과가 아닐까요?

ruddks1001 4년 전 0

djm03178 4년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말