글 읽기 - 문제의 정답은 다 맞으나 시간초과가 나네요 도와주세요!!

cdt416z 4년 전 0

정확하게 시간초과가 어디서 나는지를 모르겠습니다

1 :

line 13 ~ 21

2 :

line 22 ~ 34

둘중 한 곳일거 같은데 어디인가요,,?? 조언 부탁드립니다

#include <stdio.h>

long long dp[100001] = { 0 };

long long Min(long long a, long long b){
    return a < b? a : b;
}

int main(){
    long long N;
    scanf("%lld", &N);
    long long pow;
    for(long long i = 1; i <= N; i++){
        if(i * i > N){
            pow = i - 1;
            i = N + 1;
        }
    }
    for(long long i = 1; i <= pow; i++){
        dp[i * i] = 1;
    }
    for(long long i = 2; i <= N; i++){
        if(dp[i] == 0){
            long long last = dp[i - 1] + 1;
            long long min = 300000;
            for(long long j = 1; j < i; j++){
                if(dp[j] + dp[i - j] < min){
                    min = dp[j] + dp[i - j];
                }    
            }
            min = Min(min, last);
            dp[i] = min;
        }
    }
	printf("%lld", dp[N]);    
    return 0;
}

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

문제

문제

출처

ICPC

문제의 정답은 다 맞으나 시간초과가 나네요 도와주세요!!

cdt416z 4년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말