글 읽기 - 시간초과가 뜹니다

kkyung0321 5년 전 0

여러 테스트 케이스 해보면 답은 나오는거 같은데 시간 초과가 뜹니다. 해결법이 있을까여?? 아니면 점화식을 다르게 짜야하나여?? 큰수 넣어봐도 2초안에 나오는거 같은데;;

다른 질문좀 하자면 시간 측정도 한번씩 해보는데 같은 테스트케이스로 시간측정을 하는데도 시간이 조금씩 다르게 나오더라고요 원래 이런가요?? (_ _)

#include <algorithm>
#include <iostream>
#include <vector>
#include <string>

int n;

int cache[100001];

int dp(int);

int min(int a, int b) {
	if (a <= b)
		return a;
	else return b;

}

int main(void) {
	
	std::cin >> n;

	for (int i = 0; i < 100001; i++) {
		cache[i] = 100000;
	}

	int temp = dp(n);

	std::cout << temp;

	return 0;

}

int dp(int num) {

    // 밑에 경우들은 자기 자신을 2로 나눈값의 제곱이 자기자신을 초과하지 않아서 기저 베이스로 했음
	if (num <= 0)
		return 0;
	if (num == 1)
		return 1;
	if (num == 2)
		return 2;
	if (num == 3)
		return 3;
	if (num == 4)
		return 2;
	if (num == 5)
		return 2;

	int &ref = cache[num];

	if (ref != 100000)
		return ref;

	int temp2 = 0;
    
    //함수 파라미터 num을 반으로 쪼개고 만약 그 제곱수가 num보다 더 큰경우 반으로 쪼갠수를
    //다시 반으로 제곱값이 num보다 작을때까지 실행
	for (int i = (int)(num / 2); i >= 1; ) {
		if (i*i > num) {
			i = (int)(i / 2);
			continue;
		}
		else {
            // 값을 구했으면 예를들어 100을 위의 실행을 통해 처음구하면 j=6이 나오는데
            // j=10 부터 시작해서 밑으로 내려가게끔 하려고 하므로 제곱을 해서 그게 num보다 클테까지 반복
            //하다가 -1 해서 temp2 반환
			for (int j = i; ; j++)
				if (j*j > num) {
					temp2 = j-1;
					break;
				}
		}
		if (temp2 != 0)
			break;
	}

    //temp2값을 받아서 -1씩 빼가면서 최소값을 구함
    // 저기 for문 조건을 i>=temp2/2로 시간 단축해도 시간 초과가 떠요ㅠㅠ
	for (int i = temp2; i >= 1; i--) {
		ref = min(ref, dp(num - (i * i)) + 1);
	}

	return ref;
}

indioindio 5년 전 1

100000 같은 큰 수를 넣으면

i*i -> 2,500,000,000

으로 오버플로우가 납니다.

kkyung0321 5년 전 1

ㄴ 감사합니다 int형 다 long long 으로 고치니깐 나왔습니다. ㅎㅎ

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

문제

문제

출처

ICPC

시간초과가 뜹니다

kkyung0321 5년 전 0

indioindio 5년 전 1

kkyung0321 5년 전 1

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말