글 읽기 - 시간 초과 질문드립니다.

dlswlfl 5년 전 0

어디에서 시간 초과가 나는 걸까요? 컴파일과 출력은 잘 됩니다 ..

//https://www.acmicpc.net/problem/15857

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<vector>

using namespace std;

int N,M;
int res[8];								//초기값을 입력 받을 배열
int visited[8];							//방문 기록을 저장 할 배열
int store[8];
vector<int> vc;							//지금까지 나온 수열을 저장 할 벡터
int check_cnt;							//check함수에서 loop를 빠져나올지 정할 변수
int cnt;


int check() {		//배열과, 횟수를 입력 받아 벡터에 있는지를 확인

	if (cnt == 0) {
		cnt++;
		for (int i = 0; i < M; i++) {		//loop에 없는 것이니까 벡터에 추가
			vc.push_back(store[i]);
		}
		return 1;
	}
	else {
		for (int i = 0; i < cnt; i++) {
			check_cnt = 0;					//있는것인지 확인 할 변수를 0으로 초기화		
			for (int j = 0; j < M; j++) {
				if (store[j] == vc[j + i*M]) check_cnt++;		//check_cnt가 N이 되면 있는것
			}
			if (check_cnt == M) return 0;
		}									//loop를 빠져 나왔다는건 기존의 것중 없다는 뜻

		for (int i = 0; i < M; i++) {		//loop에 없는 것이니까 벡터에 추가
			vc.push_back(store[i]);
		}
		cnt++;								//cnt값 증가
		return 1;							//1 리턴->if 함수로 판별할때 사용
	}
}

void dfs(int turn) {

	if (turn == M) {
		if (check()) {						//벡터에 없던것이면 출력
			for (int i = 0; i < M; i++)
				cout << store[i]<<" ";
			cout << '\n';
		}
		else return;						//있던것이면 return
	}

	for (int i = 0; i < N; i++) {
		if (!visited[i]) {
			visited[i] = 1;
			store[turn] = res[i];
			dfs(turn + 1);
			visited[i] = 0;
		}
	}
}

int main() {
	cin >> N >> M;
	for (int i = 0; i < N; i++)
		cin >> res[i];

	sort(res, res + N);
	dfs(0);
}

djm03178 5년 전 1

8 8

1 2 3 4 5 6 7 8

dlswlfl 5년 전 0

아하.. 그러면 어떤 방법으로 접근 해야 시간초과가 안나올까요?

djm03178 5년 전 1

뭔가를 검사하는 과정이 저렇게 많이 있을 필요가 없습니다. 이미 크기 순으로 정렬을 해놨으니, 앞에서부터 하나씩 고르기만 하면 됩니다. 직전에 고른 것보다 1개 뒤를 고르는 경우, 2개 뒤를 고르는 경우, ...개 뒤를 고르는 경우에 대해 각각 재귀호출만 하면 됩니다.

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

문제

문제

출처

ICPC

시간 초과 질문드립니다.

dlswlfl 5년 전 0

djm03178 5년 전 1

dlswlfl 5년 전 0

djm03178 5년 전 1

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말