글 읽기 - lower_bound, upper_bound 와 직접구현의 차이를 알려주세요

tprjs456 2년 전 0

lower_bound, upper_bound 를 사용했을때는 통과가 가능했지만 이 알고리즘 직접 구현해보았는데 시간초과가 발생하였습니다.

감히 똑같이 구현했다고는 말 못하지만 그래도 어떤 차이를 갖고 있는 알려주시면 감사하겠습니다!

부탁드립니다!

//직접 구현 코드
#include<iostream>
#include<string>
#include<vector>
#include<algorithm>

#define endl "\n"
#define MAX 1000000
using namespace std;

int T, N, M;
int A[1111];
int B[1111];


void Input() {
	cin >> T;
	cin >> N;
	for (int i = 0; i < N; i++) { cin >> A[i]; }
	cin >> M;
	for (int i = 0; i < M; i++) { cin >> B[i]; }
}
long long result = 0;
vector<int> AA;
vector<int> BB;

void Solution() {
	for (int i = 0; i < N; i++) {
		int sum = 0;
		for (int j = i ; j < N; j++) {
			sum += A[j];
				AA.push_back(sum);
		}
	}
	for (int i = 0; i < M; i++) {
		int sum = 0;
		for (int j = i; j < M; j++) {
			sum += B[j];
				BB.push_back(sum);
		}
	}
	sort(AA.begin(), AA.end());

	for (int i = 0; i < BB.size(); i++) {
		int cnt = 0;
		for (int j = 0; j < AA.size(); j++) {
			if(BB[i]+AA[j]==T){
				while (BB[i] + AA[j]==T && j < AA.size()) { j++; cnt++; }
				break;
			}
			
		}
		result += cnt;
	}
	cout << result;
}

void Solve() {
	Input();
	Solution();
}

int main(void) {
	ios::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);

	Solve();

	return 0;
}




//lower_bound, upper_bound 사용 코드
#include<iostream>
#include<string>
#include<vector>
#include<algorithm>

#define endl "\n"
#define MAX 1000000
using namespace std;

int T, N, M;
int A[1111];
int B[1111];


void Input() {
	cin >> T;
	cin >> N;
	for (int i = 0; i < N; i++) { cin >> A[i]; }
	cin >> M;
	for (int i = 0; i < M; i++) { cin >> B[i]; }
}
long long result = 0;
vector<int> AA;
vector<int> BB;

void Solution() {
	for (int i = 0; i < N; i++) {
		int sum = 0;
		for (int j = i ; j < N; j++) {
			sum += A[j];
				AA.push_back(sum);
		}
	}
	for (int i = 0; i < M; i++) {
		int sum = 0;
		for (int j = i; j < M; j++) {
			sum += B[j];
				BB.push_back(sum);
		}
	}
	sort(AA.begin(), AA.end());

	for (int i = 0; i < BB.size(); i++) {
		int low = lower_bound(AA.begin(), AA.end(), T - BB[i])-AA.begin();
		int high = upper_bound(AA.begin(), AA.end(), T - BB[i]) - AA.begin();

		result += high - low;
	}
	cout << result;
}

void Solve() {
	Input();
	Solution();
}

int main(void) {
	ios::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);

	Solve();

	return 0;
}

oknook 2년 전 1

lower_bound는 이분탐색으로 구현되어 있으며 이분탐색의 시간 복잡도는 log(N)입니다.

tprjs456 2년 전 0

알려주셔서 감사합니다!!

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

문제

문제

출처

ICPC

lower_bound, upper_bound 와 직접구현의 차이를 알려주세요

tprjs456 2년 전 0

oknook 2년 전 1

tprjs456 2년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말