글 읽기 - 이분탐색 부분 틀린점을 못찾겠습니다..

ll1000wooll 7년 전 0

알고리즘은 맞는 것 같아서

이분탐색 하는 부분을 STL로 사용했더니

패스를 하네요...

제가 구현한 b함수의 이분탐색 부분 중 어느 부분이 잘못되었는지 잘모르겠습니다..

디버깅을 해도 제대로 탐색을 하는데...ㅠ.ㅠ

고수님들의 조언 부탁드리겠습니다.

#include <stdio.h>
#include <iostream>
#include <cstdio>
#include <algorithm>
using namespace std;
int n;
int arr[100002];
int check[100002];
int cnt;
int b(int x) {
	int l = 0;
	int r = cnt;
	int ans = 0;
	while (l <= r) {
		int mid = (l + r) / 2;
		if (arr[mid] >= x) { //줄여나감
			ans = mid;
			r = mid - 1;
		}
		else {
			l = mid + 1;
		}
	}
	return ans;
}
int main() {
	scanf("%d", &n);
	for (int i = 0; i < n; i++) {
		scanf("%d", arr + i);
	}
	check[cnt++] = arr[0];
	for (int i = 1; i < n; i++) {
		if (arr[i] > check[cnt - 1]) {
			check[cnt++] = arr[i];
		}
		else {
			int num = b(arr[i]);
			//int num = lower_bound(check, check + cnt, arr[i]) - check;
			check[num] = arr[i];
		}
	}
	cout << n - cnt << "\n";
	return 0;
}

pichulia 7년 전 1

이분검색을 이상한 배열에서 돌리고있네요.

ll1000wooll 7년 전 0

어처구니없는 실수를 했네요...ㅜㅜ정말감사합니다!

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

문제

문제

출처

ICPC

이분탐색 부분 틀린점을 못찾겠습니다..

ll1000wooll 7년 전 0

pichulia 7년 전 1

ll1000wooll 7년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말