글 읽기 - 왜 시간초과가 날까요 ㅜㅜ

gustjq1101 4년 전 0

나름 divide and conquer로 O(N lgN) 으로 짰다고 생각했는데 시간초과가 나요 ㅜㅜ 뭐가 문제일까요,,?

#include <iostream>
#include <algorithm>
#include <vector>

using namespace std;
vector<int> v;
int n;
int s;
int INF = (int)1e5 + 1;

int daq(int a, int b) {

	if (a == b) {
		if (v[a] >= s) return 1;
		return INF;
	}
	int ret;
	int mid = (a + b) / 2;
	int l = mid, r = mid + 1;
	int sum = v[l] + v[r];
	while (l != 0 && r != n - 1 && sum < s) {
		if (v[l - 1] < v[r + 1]) sum += v[++r];
		else sum += v[--l];
	}
	while (l != 0 && sum < s) {
		sum += v[--l];
	}
	while (r != n - 1 && sum < s) {
		sum += v[++r];
	}

	if (sum >= s)
		ret = r - l + 1;
	else
		ret = INF;
	return min({ ret, daq(a, mid), daq(mid + 1, b) });
}


int main() {
	ios::sync_with_stdio(false);
	cin.tie(0);
	cin >> n >> s;
	v.resize(n);
	for (int i = 0; i < n; i++) cin >> v[i];
	int result = daq(0, n - 1);
	cout << (result != INF ? result : 0);
	return 0;
}

gustjq1101 4년 전 0

결국 투포인터를 써서 풀었습니다만,

위에 올린 코드도 O(NlogN)에 작동하기 때문에 입력값 최대인 10만에서도 잘 작동할거라 판단했는데 이상하네요 ㅜㅜ..

gustjq1101 4년 전 0

21 25 28 라인 돌릴때 a ~ b 범위를 돌려줘야하는데 0 ~ n - 1범위를 돌려줘서 시간초과가 났네요

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

문제

문제

출처

ICPC

왜 시간초과가 날까요 ㅜㅜ

gustjq1101 4년 전 0

gustjq1101 4년 전 0

gustjq1101 4년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말