글 읽기 - 시간 초과를 어떻게 해결할 수 있을까요?

testtest4 4년 전 0

이 문제는 주어진 n의 최대 크기가 20이라 그렇게 크지 않다고 생각했습니다

또한 자료형 set을 사용해 중복되는 값도 제거되어 dfs로 풀 수 있다고 생각했는데 시간 초과가 뜨네요

제 코드를 뭔가 고칠만한게 있을까요?

한번만 읽어주시고 힌트를 주시면 감사하겠습니다!

#include <iostream>
#include <vector>
#include <algorithm>
#include <math.h>
#include <string>
#include <string.h>
#include <map>
#include <set>

using namespace std;

int arr[4] = { 1,5,10,50 };
int n;

set<int> vec;

void fundfs(int start, int sum) {
	if (start == n) {
		vec.insert(sum);
		return;
	}

	for (int i = 0; i < 4; i++) {
		fundfs(start + 1, sum + arr[i]);
	}
}


int main() {

	cin >> n;

	fundfs(0, 0);

	cout << vec.size();
}

miles94 4년 전 0

set 을 통해 그동안 쌓인 sum 값들을

처음 부터 비교하면서 있는지 없는지 추가하는 내부 알고리즘에 의해

시간초과가 걸리는 것 같습니다.

set 을 사용하지마시고, 최대 50*20+1 의 크기를 갖는 boolean check array 를 만드셔서

dfs 종료 조건에 check array 의 값이 false 이면 true로 바꾸면서 cnt 증가시키는 방식으로

구현하시면 될 것 입니다.

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

문제

문제

출처

ICPC

시간 초과를 어떻게 해결할 수 있을까요?

testtest4 4년 전 0

miles94 4년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말