글 읽기 - 이 문제에서 nlogn이 실패하는 이유가 무엇일까요?

clrmt 4년 전 0

알고리즘을 한 줄로 설명하면 0번부터 i까지 합 sum의 배열을 만든 뒤 n개의 원소 각각마다 이분탐색하여 합이 m이 되는 인덱스를 찾았습니다.

예제는 맞게 나왔지만 제출하면 시간 초과가 나오네요.

nlogn은 거의 100만개까지 통과하는 것 같던데 여기서는 10000개조차 시간초과가 나는 이유가 무엇일까요?

#include <iostream>
using namespace std;

int main() {

	ios_base::sync_with_stdio(false);
	cin.tie(NULL);

	int number[10001];
	int sum_[10003];
	int *sum = sum_ + 1; // 배열 인덱스가 -1부터 시작하도록 어드레싱
	sum[-1] = 0;

	int n, m;
	cin >> n >> m;

	int i, j;

    // 입력 및 sum생성
	for (i = 0; i < n; i++) {
		cin >> number[i];
		sum[i] = sum[i - 1] + number[i];
	}

    // 이분 탐색
	int rangeMin;
	int rangeMax;
	int rangeMid;

	int count = 0;

	int a;

	for (i = -1; i < n; i++) {

		rangeMin = i;
		rangeMax = n;
		
		while (1) {

			rangeMid = (rangeMin + rangeMax) / 2;

			a = sum[rangeMid] - sum[i]; // 합계
			if (a == m) {
				count++;
				break;
			}

			if (rangeMid == rangeMin) {
				// # 실패
				break;
			}

			if (a < m) {
				rangeMin = rangeMid;
			} else {
				rangeMax = rangeMid;
			}

		}

	}

	cout << count;

}

djm03178 4년 전 1

이렇게 넣으면 무한루프를 돕니다.

1 1
2

clrmt 4년 전 0

아... 감사합니다. 이분탐색쪽 논리에 이상이 있던거였군요

clrmt 4년 전 0

마이너스 인덱스를 즐겨쓰고 있는데 여기서는 제 발목을 잡았네요.

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

문제

문제

출처

ICPC

이 문제에서 nlogn이 실패하는 이유가 무엇일까요?

clrmt 4년 전 0

djm03178 4년 전 1

clrmt 4년 전 0

clrmt 4년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말