글 읽기 - 시간 초과 질문드립니다 ㅠ

park780172 5년 전 0

이중 for문 때문에 시간 초과가 뜨는 것 같습니다.(처음 인덱스부터 계속 비교해가니..)

헌데, 이중 for문을 사용하지 않고, 시간을 줄일 방법을 찾지 못 하겠습니다.

입력 시에 혁진이가 일할 수 있는 시간을 의미하는 정수들이 오름차순으로 주어지는 것도 아닌데..(이것을 고려하여 코드를 작성해보았으나 틀렸습니다가 뜹니다.)

이중 for문을 사용하지않는 방법이 있을까요..?

힌트 주시면 정말 감사하겠습니다.

방법이 도저히 안 떠오르네요..

#include <iostream>
#include <queue>
#include <stack>
#include <cstdio>
#include <vector>
#include <cstring>
#include <string>
#include <math.h>
#include <algorithm>
#include <map>

using namespace std;

int main(void)
{
	int N = 0, M = 0;
	long long input = 0, sum = 0;

	vector<long long> v;

	scanf("%d %d", &N, &M);

	for (int i = 0; i < N; i++)
	{
		scanf("%lld", &input);

		sum += input;
		// 그 합을 vector에 저장한다.

		v.push_back(sum);
	}

	int s = v.size();
	// 벡터 사이즈를 받는다.

	for (int i = 0; i < M; i++)
	{
		long long cnt = 0;

		scanf("%lld", &input);

		for (int j = 0; j < s; j++)
		{
			// 입력한 숫자(=input)과 vector 요소들을 처음부터(인덱스 = 0) 계속 비교해간다.

			if (input <= v.at(j))
			{
				if (input == v.at(j)) ++cnt;

				break;
			}

			++cnt;
		}

		printf("%lld\n", cnt);
	}

	return 0;
}

isku 5년 전 2

안녕하세요.

30번째 줄에서 벡터에 합을 넣고 있습니다.

이 벡터에 들어가는 합들은 정렬되어 있다는 것을 생각해보시기 바랍니다!

park780172 5년 전 0

답변 정말 감사합니다!

그 부분은 알고있었는데, 어차피 결국은

밑에서 input을 입력할 때, 그 input과 vector의 원소들을 비교할 수 밖에 없지 않나요!?

또한, 밑 input이 오름,내림차순도 아니니

벡터 인덱스 0부터 검사할 수 밖에 없다 라는 것이

저의 생각입니다! ㅠ

isku 5년 전 1

벡터에 있는 값과 인풋은 비교할 수 밖에 없습니다.

인풋값을 벡터에서 찾으려고 할 때 시간복잡도가 O(n)이라면 시간초과라는 것을 질문 하신 분도 잘 알고 있습니다.

그런데 벡터에 있는 모든 값하고 비교 해야할까요? 벡터의 맨 앞부터 찾을 수도 있겠지만 뒤에서도 찾을 수 있고 중간에서도 찾을 수 있습니다.

벡터가 정렬되어 있고, 시간복잡도가 O(n)보다 빠르게 찾는 방법이 필요할 것 입니다.

park780172 5년 전 1

시간 내서 써주신 답변 감사합니다.

왜 '그 방법'이 제 머리에서 안 떠올랐는지...

되돌아보게되었습니다ㅎ

여하튼 감사합니다!!!

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

문제

문제

출처

ICPC

시간 초과 질문드립니다 ㅠ

park780172 5년 전 0

isku 5년 전 2

park780172 5년 전 0

isku 5년 전 1

park780172 5년 전 1

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말