글 읽기 - 어디가 틀렸을까요.. (인덱스 트리, LIS)

suka222 6년 전 0

LIS 문제

Binary search 이용하는거 말고.. indexed tree 써서 풀어보고 있는데요..

어디가 틀렸는지 모르겠어서 문의드립니다.

로직은 간단히 설명 드리면 입력값 범위가 커서 처음에 리넘버링하고

들어오는 값들 하나씩 처리하는데 구간 끝나는값 찾기 위해 이진탐색을 써서 탐색할 끝점을 찾고

인덱스 트리 뒤지면서 업데이트 해줬습니다..

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.Arrays;
import java.util.StringTokenizer;

// LIS2 (indexed tree 버전)
public class Main {
	static int N;
	static int[] ip = new int[1000001];
	static int[] tmp = new int[1000001];
	static int[] renum = new int[1000001];
	static int[] idx_tree = new int[(1<<21)];  // 100만개 모두 채워야할 경우 2^20 공간 필요, 트리 구성은 2^21
	static int base;
	static int cnt, pos;
	static int ans;
	
	public static void main(String[] args) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
		
		N = Integer.parseInt(br.readLine());
		StringTokenizer stk = new StringTokenizer(br.readLine());
		for(int i=1; i<=N; i++){
			ip[i] = Integer.parseInt(stk.nextToken());
			tmp[i] = ip[i];
		}
		
		Arrays.sort(tmp, 1, N+1);
		renum[1] = tmp[1];
		cnt = 2;
		for(int i=2; i<=N; i++){
			if(tmp[i] != tmp[i-1]) renum[cnt++] = tmp[i];
		}
		cnt--;
		
		base = 1 << (int) Math.ceil(Math.sqrt(cnt));
		
		// tree 초기화 없음
		
		for(int i=1; i<=N; i++){
			pos = binary_search(1,cnt,ip[i]);
			
			int curr = query_tree(1,pos-1);
			update_tree(pos, curr+1);
		}
		
		ans = query_tree(1,cnt);

		
		bw.write(String.valueOf(ans)+"\n");
		
		bw.flush();
		bw.close();
	}

	public static int query_tree(int start, int end) {
		int ret = 0;
		
		start = start + base - 1;
		end = end + base - 1;
		
		while(start<=end){
			if(start % 2 == 1){
				ret = Math.max(ret, idx_tree[start]);
				start++;
			}
			if(end % 2 == 0){
				ret = Math.max(ret, idx_tree[end]);
				end--;
			}
			
			start>>=1;
			end>>=1;
		}
		
		return ret;
	}

	public static void update_tree(int idx, int val) {
		idx += base - 1;
		idx_tree[idx] = val;
		
		while(idx > 1){
			idx >>= 1;
			idx_tree[idx] = Math.max(idx_tree[2*idx],idx_tree[2*idx + 1]);
		}
	}

	public static int binary_search(int start, int end, int val) {
		int ret = -1;
		
		while(start<=end){
			int mid = (start + end) >> 1;
			if(renum[mid] < val){
				start = mid + 1;
			}else if(renum[mid] > val){
				end = mid - 1;
			}else{
				ret = mid;
				break;
			}
		}
		return ret;
	}
}

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

문제

문제

출처

ICPC

어디가 틀렸을까요.. (인덱스 트리, LIS)

suka222 6년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말