글 읽기 - 이진탐색으로 해결 불가능한가요? 도와주세요

iljimae 7년 전 0

문제: N과 L이 주어질 때, 합이 N이면서, 길이가 적어도 L이면서 가장 짧은 연속된 음이 아닌 정수 리스트를 구하는 프로그램을 작성하시오.

이 문제를 해결하기위해 부분합 배열 psum[]을 먼저 채워넣고 어떤 범위 [a,b] 사이의 값들을 모두 더했을때 N이 되기위해서는 psum[b]-psum[a-1] = N 을 만족해야하니까 모든 a 에 대해서 (a의 범위 0~50000, 0 일때는 예외처리) psum[a-1]+N 이 psum[] 에 존재하는지 이진탐색으로 확인하는 방법을 사용했는데 4% 정도에서 틀립니다. 뭐가 틀렸는지 알려주실 수 있나요? 아니면 반례 데이터를 주셔도 됩니다. 감사합니다!

#include <iostream> 
#include <cstdlib> 
#include <algorithm> 
using namespace std; 

#define INF 987654321

long long psum[50000]; 

int main(){
	ios_base::sync_with_stdio(false); 
	cin.tie(NULL); 
	int N,L;  
	cin >> N >> L;  
	psum[0] = 0;  
	for (int i = 1; i < 50000; i++){
		psum[i] = psum[i-1]+i;  
	}
	int len = INF;  
	int start = -1,end = -1; 
	for (int i = 0; i < 50000; i++){
		// binary search for (N+psum[i-1]) 
		int l = 0, r = 50000, val = -1; 
		while (l != r){
			int m = (l+r)/2; 
			int add = (i == 0 ? psum[0] : psum[i-1]);  // taking care of edge case: when 0 is included in the sequence. 
			if (psum[m] == N+add){
				val = m; 
				break; 
			}else if (psum[m] < N+add){
				l = m+1;  
			}else r = m; 
		}  
		if (val != -1){
			if (start == -1 && end == -1){
				if (val-i+1 >= L){
					start = i, end = val; 
					len = end-start+1;  
				}
			}else{	
				if (val-i+1 >= L && val-i+1 < len){
					start = i, end = val; 
					len = end-start+1;  
				}
			}
		}
	}
	if ((start == -1 && end == -1) || (len > 100)){ // no such sequence found, or if the length of the sequnce is greater than 100. 
		cout << -1 << endl; 
	}else{
		for (int i = start; i <= end; i++){
			cout << i << " ";  
		}
		cout << endl; 
	}
	return 0; 
}

koosaga 7년 전 3

999999999 2 를 생각해보세요

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

문제

문제

출처

ICPC

이진탐색으로 해결 불가능한가요? 도와주세요

iljimae 7년 전 0

koosaga 7년 전 3

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말