글 읽기 - O(nlogn) 관련문의

heehcs 6년 전 0

http://www.geeksforgeeks.org/l...

참고해서 O(nlogn) 방법으로 풀었습니다.

23%정도에서 틀리는데요,

논리적으로 충분하지 못한 부분 알려주시면 감사하겠습니다.

#pragma warning(disable:4996)
#define loop(i,start,stop) for(int i = start; i < stop; i++)
#include <stdio.h>
#include <iostream>
using namespace std;
int N;
int a[1001];
int d[1001];

int bs(int target, int l, int r) {
	if (r - l <= 1) {
		return r;
	}
	int mid = l + (r - l) / 2;
	if (mid == 0) {
		return mid;
	}

	if (d[mid - 1] < target &&target <= d[mid]){
		return mid;
	}
	else if (target <= d[mid - 1]) {
		return bs(target, l, mid - 1);
	}
	else if(target > d[mid]){
		return bs(target, mid, r);
	}
}

void solve() {
	d[0] = a[0];
	int len = 1;
	loop(i, 1, N) {
		if (a[i] < d[0]) {
			d[0] = a[i];
		}
		else if (a[i] > d[len - 1]) {
			d[len++] = a[i];
		}
		else {
			int p = bs(a[i], 0, len);
			d[p] = a[i];
		}
	}
	printf("%d\n", len);
}
void init(){
	ios::sync_with_stdio(false);
//	freopen("11053.data", "r", stdin);
	scanf("%d", &N);
	loop(i, 0, N) {
		scanf("%d", a + i);
	}
}
int main() {
	init();
	solve();
}

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

문제

문제

출처

ICPC

O(nlogn) 관련문의

heehcs 6년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말