글 읽기 - 세그먼트트리 시간 초과

lee0289 5년 전 0

백준 중급 강의 소스 거의 그대로 구현했는데요.

시간 초과가 나네요.

어느 부분을 수정해야 시간을 단축할 수 있을까요?

#include <iostream>

using namespace std;
int a[100001];
int tree[300001];

// 재귀호출 이용, 받은 배열을 이용해 세그먼크 트리를 만듬 
void init(int node, int start, int end) {
	if(start == end) { // 리프노드, 구간의 크기:1 
		tree[node] = a[start];
	} else {
		init(node*2, start, (start+end)/2); // left
		init(node*2+1, (start+end)/2+1, end); // right
		tree[node] = min(tree[node*2], tree[node*2+1]);
	}
}

// 만들어 놓은 세그먼트 트리를 검색하여, 최소값을 구할 수 있다. 
// 구하려는 범위를 i, j로 놓고 시작, 끝 값을 start, end로 넣는다. 
int query(int node, int start, int end, int i, int j) {
	if(i > end || j < start) return -1; // 구간이 겹치지 않음
	if(i <= start && end <= j) return tree[node]; // 구간을 포함하는 경우
	
	int m1 = query(2*node, start, (start+end)/2, i, j); // 왼쪽
	int m2 = query(2*node+1, (start+end)/2+1, end, i, j); // 오른쪽
	
	if(m1 == -1) return m2;
	else if(m2 == -1) return m1;
	else return min(m1, m2); 
} 

int main() {
	int n, m;
	scanf("%d", &n);
	scanf("%d", &m);
	 
	int start_range; 
	int end_range;
	
	for(int i=0; i<n; i++) scanf("%d", &a[i]);
	
	for(int i=0; i<m; i++) {
		scanf("%d", &start_range);
		scanf("%d", &end_range);
		
		init(1, 0, n-1); // 세그먼트 트리 구조를 만듬 -> tree가 생성됨 
	
		int ans = query(1, 0, n-1, start_range-1, end_range-1); 
	
		printf("%d\n", ans); 
		
	}
	
	
	return 0;
}

chogahui05 5년 전 1

init를 어디에 호출하셨나요?

lee0289 5년 전 0

감사합니다. 바보같이 for문 안에 넣었네요

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

문제

문제

출처

ICPC

세그먼트트리 시간 초과

lee0289 5년 전 0

chogahui05 5년 전 1

lee0289 5년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말