글 읽기 - 시간초과 문제 질문입니다! (도와주세요..)

persona_k 4년 전 0

안녕하세요.

사실 질문을 하기 전에 질문게시판에서 먼저 보고 나서 추가적으로 질문을 드립니다.

저의 경험담은 다음과 같습니다.

처음에는 0~m-1 까지로 재귀로 탐색 -> 시간초과

두번째로는 전역변수로 v와 visit를 초기화하는 과정에서 시간초과가 날 수도 있겠구나 싶어서 매개변수로 넣고 탐색 -> 시간초과

세번째로는 나름 줄여본다고 규칙을 찾아서 수정한 것이 입력받은 m을 루트를 씌운 후 m에 -2를 한 cycle 만큼을 로또번호를 뽑기를 재귀로 탐색 -> 시간초과

질문을 검색해보니 재귀로 탐색을 하나 메모이제이션을 추가로 적용해야 시간초과가 나지 않는다고 하는데, 사실 이 부분이 이해가 안갑니다..

어떻게 중복이 있을 수 있을까요??

제가 짠 코드로는 로또 번호가 1에서 시작해서 차곡차곡 순서대로 저장이 되어있는 상태에서 재귀로 짜게 되면 깊이 들어가면서 하나씩 로또 번호가 이전 번호보다 2배보다 크거나 같으면 다음 번호로 이동하면서 로또번호를 찾아가도록 만든 재귀인데, 중복되는 구간이 없다고 생각되는데 저의 생각이 틀린 것인가요?

아래 코드도 첨부했습니다.

읽어주셔서 감사합니다.

#include <iostream>
#include <vector>
#include <string>
#include <cmath>
using namespace std;

int n, m, ans, tc;

//idx는 해당 로또번호의 인덱스
//num은 해당 로또번호의 값
//cnt는 지금까지 뽑은 경우의 수
//visit은 방문 배열 (이전에 뽑았다면 true, 아니라면 false)
//v는 해당 로또 번호를 담고 있는 배열
void dfs(int idx, int num, int cnt, vector<bool> visit, vector<int> v){
	visit[idx] = true; //번호 사용표시 

	if(cnt == n){ //로또를 다 골랐으면 
		ans++;
	}else{
		for(int i=idx+1; i<m; i++){
			if(visit[i] == true) continue;
            //이전에 고른 수보다 적어도 2배가 되도록 한다.
			if(num * 2 <= v[i] && v[i] <= m){
				dfs(i, v[i], cnt+1, visit, v);
			}
		}
	}
	visit[idx] = false; //backtracking
}

int main(){
	cin>>tc;
	for(int testCase = 0; testCase<tc; testCase++){
		vector<int> v; //로또를 담을 배열
		cin>>n>>m; 
		ans = 0;
		for(int i=0; i<m; i++){ //로또 번호 넣기
			v.push_back(i+1);
		}
        //찾은 규칙을 이용해 적용
		int cycle = (int)sqrt(m) - 2;
		for(int i=0; i<cycle; i++){
			vector<bool> visit(m); //방문 배열 초기화
			dfs(i, v[i], 1, visit, v); //로또 번호 뽑기
		}
		cout<<ans;
	}
	return 0;
}

sait2000 4년 전 0

일단 visit과 v가 매번 복사되고 있습니다. 다음부턴 레퍼런스를 사용해보세요.

왜 다음부터냐면 v가 필요 없습니다. v[i] == i + 1이니까요.

그리고 생각해보면, 중요한 건데, visit이 필요가 없습니다. 전에 고른 것보다 큰 것만 따지는데 그걸 이미 고른 경우가 존재할까요?

즉, 실제로 dfs가 알아야 할 정보는 지금 고를 수 있는 최소의 값만 알면 됩니다. visit의 내용물은 중요하지 않습니다. 이렇게 생각해보면 중복이 존재함을 알 수 있죠. 다음처럼요.

1 2 6 ...

1 3 6 ...

저 두 번호 뒤쪽에 올 수 있는 조합은 완전히 똑같습니다. 따라서 이러한 부분을 메모이제이션할 수 있겠습니다. 근데 이렇게 풀리나 모르겠네요. 조금 다르게 dp를 해서.

근데 sqrt는 뭔가요?

persona_k 4년 전 0

@sait2000

읽어주셔서 감사합니다.

말씀하신대로 visit배열을 쓰지않아도 되겠네요!!

레퍼런스 부분이라면 memset을 의미하는건가요??

제가 중간에 sqrt를 쓴 이유는

테케에 4 10을 예를 들면

항상 시작하는 번호는 1밖에 없습니다.

4 20으로 예를 들면

항상 시작하는 번호는 1, 2

4 30으로 예를 들면

항상 시작하는 번호는 1, 2, 3 입니다.

따라서 다음과 같은 규칙을 발견했습니다.

인풋으로 m을 받아오면 해당 m을 루트씌운 후 2를 빼준만큼만 시작하면 되겠다 싶어서 그렇게 구현했습니다.

집에 가서 다시한번 수정해서 해보겠습니다.

감사합니다 !!

sait2000 4년 전 0

이런 경우는 어떨까요. 첫번째 경우는 1부터 10까지가 다 되네요.

sait2000 4년 전 0

레퍼런스는 c++ 레퍼런스라고 검색을 해보세요. 꼭 해보세요

persona_k 4년 전 0

@sait2000

아 저런 경우도 있군요..

네 꼭해볼게요. 감사합니다!

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

문제

문제

출처

ICPC

시간초과 문제 질문입니다! (도와주세요..)

persona_k 4년 전 0

sait2000 4년 전 0

persona_k 4년 전 0

sait2000 4년 전 0

sait2000 4년 전 0

persona_k 4년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말