글 읽기 - 제 코드가 시간초과가 발생하지 않는 이유는 뭘까요?

jumpingz 6년 전 0

예전에 짯던 코드였는데 시간복잡도가 N^2 인거 같은데 시간초과가 발생하지 않는데 의문이 듭니다.

매순간 가장 큰값을 찾아서 그 위치만큼 값을 계산하고 시작위치를 큰값이 있는 위치로 이동하는 방식으로 구현한건데

만약 데이터가 100 99 98 97 ... 이런식으로 100000개가 있다면 시간 초과가 발생해야하는 것같습니다만 여전히 맞았다고 뜨는군요.

제가 잘못생각하고 있는건지 아니면 저런 테스트케이스가 없는건지 알고 싶습니다.

#include <cstdio>
#include <vector>
#pragma warning(disable:4996)
using namespace std;

int main()
{
	int start, data, index, N, T, cnt = 1;
	long long int result;
	scanf("%d", &T);

	for (int i = 0; i < T; i++)
	{
		scanf("%d", &N);
		vector<int> v(N);

		for (int j = 0; j < N; j++)
			scanf("%d", &v[j]);

		start = 0;	result = 0;
		while (start < N)
		{
			data = 0;
			for (int j = start; j < N; j++)
			{
				if (v[j] > data)
				{
					data = v[j];
					index = j;
				}
			}

			for (int j = start; j < index; j++)
				result += (v[index] - v[j]);

			start = index + 1;
		}

		printf("#%d %lld\n", cnt++, result);
	}

	return 0;
}

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

문제

문제

출처

ICPC

제 코드가 시간초과가 발생하지 않는 이유는 뭘까요?

jumpingz 6년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말