글 읽기 - 더 좋은 방법이 있을까요?

yeop9657 5년 전 0

안녕하세요 :)

순서 쌍 문제를 풀면서 시간초과가 자꾸 발생해서 혹시 더 좋은 방법이 있나요?

#include <vector>
#include <cstdio>
#include <algorithm>
using namespace std;

long long answer = 0;
int value[100001] = { 0, };

int main(void)
{
	unsigned int number = 0;
	scanf("%d", &number);

	for (unsigned int ii = 0; ii < number; ii++) { scanf("%d", &value[ii]); }

	vector<int> permutation = vector<int>(number);
	permutation[number - 1] = permutation[number - 2] = 1;

	vector<int> mul;

	do {

		register unsigned int index = 0;
		for (auto begin = permutation.begin(); begin != permutation.end(); begin++, index++) {
			if (*begin == 0) { continue; }
			mul.push_back(value[index]);
		}

	} while (next_permutation(permutation.begin(), permutation.end()));

	for (unsigned int ii = 0, length = mul.size(); ii < length - 1; ii += 2) {
		answer += mul[ii] * mul[ii + 1];
	}

	printf("%lld\n", answer);

	return 0;
}

hello70825 5년 전 0

순열때문에 시간초과가 나고 있습니다.

밑 소스 코드 방식이 문제에서 말하는 작동 방식인데, 이중 for문을 이용하면 O(N!)으로 시간초과가 나옵니다.

그래서 for문 한 개와 밑 소스 코드 2~3줄을 한번에 처리할 수 있는 식을 만들어 O(N)으로 풀면 됩니다.

for문 i는 0부터 N-1까지
    for문 j는 i+1부터 N까지
        answer+=value[i]*value[j]

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

문제

문제

출처

ICPC

더 좋은 방법이 있을까요?

yeop9657 5년 전 0

hello70825 5년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말