글 읽기 - 순열을 이용해서 푸는방법 질문드려요!

wjavm2 4년 전 0

백준님 강의듣고 백트래킹으로도 풀어보고 순열로도 풀어보고있습니다!

그런데 제가 순열 STL쓰는법이 익숙치않다보니 자꾸 시간초과가 뜹니다!

제가 검색해본결과로는 순열로 조합을 구현할때 반드시 sort를 해주어야 한다그래서 sort도 해주었는데

제가 잘못알고있는부분이 어느곳인가요?

자꾸시간초과가 나는 이유가 뭘까요...?

#include<iostream>
#include<algorithm>
#include<vector>
#include<string>

using namespace std;

char oper[10];
int k;
vector<string>result;

bool isOk(vector<int> V);
bool cmp(int a, int b)
{
	return a > b;
}

int main()
{
	cin >> k;
	for (int i = 0; i < k; i++)
	{
		cin >> oper[i];
	}

	vector<int>Max;
	vector<int>Min;
	for (int i = 0; i <= k; i++)
	{
		Min.push_back(i);
	}
	sort(Min.begin(), Min.end());

	for (int i = 9; i >= 9- k; i--)
	{
		Max.push_back(i);
	}
	sort(Max.begin(), Max.end(),cmp);

	do {
			
		if (isOk(Min))
		{
			string R = "";
			for (int i = 0; i < Min.size(); i++)
			{
				R += to_string(Min[i]);
			}
			result.push_back(R);
		}
	
	} while (next_permutation(Min.begin(), Min.end()));

	do {

		if (isOk(Max))
		{
			string R = "";
			for (int i = 0; i < Max.size(); i++)
			{
				R += to_string(Max[i]);
			}
			result.push_back(R);
		}

	} while (prev_permutation(Max.begin(), Max.end()));

	string P = *max_element(result.begin(), result.end());
	string L = *min_element(result.begin(), result.end());
	cout << P << endl;
	cout << L << endl;

	//system("pause");
	return 0;
}

bool isOk(vector<int>V)
{
	for (int i = 0; i < V.size(); i++) {
		if (i + 1 >= V.size())continue;
		if (oper[i] == '<')
		{
			if (V[i] < V[i + 1]) return true;
		}
		if (oper[i] == '>')
		{
			if (V[i] > V[i + 1]) return true;
		}
		return false;
	}
}

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

문제

문제

출처

ICPC

순열을 이용해서 푸는방법 질문드려요!

wjavm2 4년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말