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

yms21888 5년 전 0

시간초과가 뜨는데 시간복잡도가 10의 7승인거 같은데 .. 왜그럴까요 ㅠ 도와주시면 감사하겠습니다...

#include <cstdio>
#include <iostream>
#include <algorithm>
#include <math.h>
#define INF 1000000
using namespace std;
// 작은 생성자를 구하는 것이면 각 자리 수의 합을 빼주면 된다

int N;
int visited[9];
int ans = INF;
void DFS(int cnt, int idx){
	if (cnt == idx){
		int sum = 0; 
		int add = 0;
		int a = cnt - 1;
		for (int i = 0; i < cnt; i++){
			sum += visited[i] * pow(10, a);
			add += visited[i];
			a--;
		}
		if (sum + add == N){
			ans = (ans > sum) ? sum : ans;
		}
		return;
	}
	else{
		for (int i = 0; i < 10; i++){
			visited[cnt] = i;
			DFS(cnt + 1, idx);
		}
	}
}
int main(void){
	ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);

	cin >> N;
	int M = N;
	int idx;
	for (int i = 7; i >= 1; i--){
		int n = pow(10, i);
		if (N / n != 0){
			idx = i;
			break;
		}
	}
	idx++;
	DFS(0, idx);
	if (ans == INF) ans = 0;
	cout << ans << endl;
	return 0;
}

djm03178 5년 전 1

pow는 실수형으로 연산하는 것이고, 실수형의 연산은 상상하시는 것보다 훨씬, 훨씬 더 느립니다. pow의 값을 미리 계산해서 배열에 저장해두기만 하면 통과됩니다.

yms21888 5년 전 0

감사합니다 !!!

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

문제

문제

출처

ICPC

시간초과가 뜹니다.

yms21888 5년 전 0

djm03178 5년 전 1

yms21888 5년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말