글 읽기 - next_permutation 함수를 이용한 문제 풀이에 대해 질문이 있습니다.

psh01312 4년 전 0

보시다시피 저는 단순하게 next_permutaion함수를 이용하여 N개의 숫자를 가진 A가 가질 수 있는 모든 경우의 수를 구한 후 이를 통해 S의 최솟값을 구하려 했습니다.

하지만 제가 예제를 적용했을때 18이 아닌 예상과 다른 결과값이 나오게 되는데 혹시 제가 문제를 푸는데 있어서 오류를 범하거나 잘못 설계한 것이 있을까요?

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

int main()
{
	int N;
	vector<int> A, B;

	int minimum = 100000;//S의 최솟값이 저장될 변수
	cin >> N;

	for (int i = 0; i < N; i++)
	{
		int num;
		cin >> num;
		A.push_back(num);
	}
	for (int i = 0; i < N; i++)
	{
		int num;
		cin >> num;
		B.push_back(num);
	}// A,B 입력

	do {
		int result = 0;//S
		for (int i = 0; i < N; i++)
		{
			result += A[i] * B[i];
		}

		if (result < minimum)
			minimum = result;// 최솟값 갱신
	} while (next_permutation(A.begin(), A.end()));

	cout << minimum << "\n";
	return 0;
	
}

djm03178 4년 전 0

next_permutation을 "처음부터 끝까지" 수행하려면 '처음' 상태를 먼저 만들어놓고 시작해야 합니다. 그 '처음'이라는 것은 원소가 오름차순으로 정렬된 상태를 의미하는데, 이 코드에는 정렬을 하는 부분이 없습니다.

그리고 이 문제를 그렇게 풀면 시간 초과를 피할 수 없습니다. 최악의 경우인 50개 원소를 next_permutation으로 전부 돌리려면 50! 정도의 시간이 걸리는데 이 값은 30414093201713378043612608166064768844377641568960512000000000000 라는 어마어마하게 큰 수로, 우주가 멸망할 때까지도 다 돌려볼 수가 없는 수치입니다.

psh01312 4년 전 0

그러면 직접 가능한 A를 모두 구해서 Sum을 계산한다음 minimum을 구하는 방식 이외에 별도의 수식이나 규칙을 통해서 한번에 minimum을 구하는 방식이 있을까요??

djm03178 4년 전 1

그리디하게 풀 수 있습니다.

psh01312 4년 전 0

감사합니다. 많은 도움 되었습니다.

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

문제

문제

출처

ICPC

next_permutation 함수를 이용한 문제 풀이에 대해 질문이 있습니다.

psh01312 4년 전 0

djm03178 4년 전 0

djm03178 4년 전 0

psh01312 4년 전 0

djm03178 4년 전 1

psh01312 4년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말