글 읽기 - 이분탐색풀이

anginjunddi 2년 전 3

그냥 지나가시면서 이런것도 있구나 참고하시길 바래요.

물론 DP풀이가 더 빠를것 같지만 제가 DP는 할 줄 몰라서 이렇게 풀어봤습니다.

#include <cstdio>
#include <algorithm>
using namespace std;
 
int arr[3010];
long long int search(int start, int end, int x, int gap){
	int k = (lower_bound(arr+start, arr+end, x)-arr);
	if(arr[k]==x) return arr[k]+search(k+1, end, arr[k]+gap, gap);
	return 0;
}
int main(){
	int n;
	long long int sum, res = 0;
	scanf("%d", &n);
	for(int i = 0; i < n; i++){
		scanf("%d", &arr[i]);
	}
	for(int i = 0; i < n; i++){
		for(int k = i+1; k < n; k++){
			sum = arr[i]+arr[k];
			sum += search(k+1, n, arr[k]+(arr[k]-arr[i]), arr[k]-arr[i]);
			if(sum>arr[i]+arr[k]&&sum>res) res = sum;
		}
	}
	printf("%lld", res);
}

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

문제

문제

출처

ICPC

이분탐색풀이

anginjunddi 2년 전 3

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말