글 읽기 - 순열로 문제해결시도했는데 똑같은 게 두번씩 출력됩니다.

shinbian11 3년 전 0

예제입력을 그대로 넣으면

7 1 2 3 4 5 6 7 일떄는 정상적으로 잘 출력되는데

8 1 2 3 5 8 13 21 34 일때는 두번씩 출력되는 이유가 뭔가요??

//c++

#include <bits/stdc++.h>
#define F_I ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);

using namespace std;
typedef long long ll;

//vector<int> lotto;
int sorting(vector<int>& a)
{
	for (int i = 0; i < 5; i++)
	{
		if (a[i] > a[i + 1])
			return 0;
	}
	return 1;
}
int main()
{
	F_I;
	
	while (true)
	{
		int n;
		cin >> n;
		if (n == 0)
			return 0;
		vector<int> a;
        a.clear();
		for (int i = 0; i < n; i++)
		{
			int m;
			cin >> m;
			a.push_back(m);
		}

		do
		{
			if (sorting(a))
			{
				for (int i = 0; i < 6; i++)
					cout << a[i] << ' ';
				cout << '\n';
			}
			
		} while (next_permutation(a.begin(), a.end()));
	}
}

pch6828 3년 전 1

1 2 3 5 8 13 21 34 일 때와
1 2 3 5 8 13 34 21 일 때, 둘의 첫번째부터 6번째 자리까지는 모두 같습니다. 이런 경우 때문에 두번씩 출력이 될것입니다.

shinbian11 3년 전 0

그럼 순열로는 저 문제를 풀기가 어렵나요? 재귀로는 풀어봐서 순열 이용해서도 풀고 싶은데 막히네요 ㅠ

순열로 풀기에는 값이 너무 큽니다. 12!개의 순열이 존재할텐데, 이 값은 대충 5억 정도 됩니다. 여기다 매 순열 처음부터 6번째자리까지 체크하는 것도 들어가기 때문에 연산이 너무 많이 필요하죠

또한 순열로 풀기에는 처음부터 여섯 자리가 모두 정렬되어 있는 경우만 허용되기 때문에 사실상 너무 많은 경우가 버려지게 됩니다.

저는 그냥 6중 for문으로 해결하긴 했네요...ㅎㅎ

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

문제

문제

출처

ICPC

순열로 문제해결시도했는데 똑같은 게 두번씩 출력됩니다.

shinbian11 3년 전 0

pch6828 3년 전 1

shinbian11 3년 전 0

pch6828 3년 전 1

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말