6603. 로또

주의사항 250121

• 인덱스 증가시킬때 i++로 넣으면 안된다.
  : 왜냐하면 인덱스를 그대로 i로 넘긴 다음에 ++이 적용되기 때문이다.
  

• 반드시 이러한 상황에서는 증감 연산자보다는 정확한 값을 명시하자.

---

순열로 풀기 241231-강의 참고.

• 입력으로 주어진 k개에서 6개의 수를 고르는 문제다.
  : 순열로 생각하기보다는 재귀로 처리해야 겠다는 생각이 들지만, 순열로도 가능하다.

• 예를 들어 로또 6개를 1로하고, 나머지를 n-6개를 0으로 삽입해놓는다.
  그리고 이들을 순열로 돌리면서 처리한다...

언제품

: 220909 11:42 ~ 11:51

알고리즘 분류

: 조합!

• 백트래킹

최종 풀이

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

int cnt = 6;
vector<int>res;

void combi(vector<int>&v, int start)
{
	if (res.size() == cnt)
	{
		//output 
		for (auto iter : res)
		{
			cout << iter << ' ';
		}
		cout << endl;
	}


	for (int i = start; i < v.size(); ++i)
	{
		res.push_back(v[i]);
		combi(v, i + 1);
		res.pop_back();

	}

}


int main() 
{
	while (1)
	{
		int n;
		cin >> n;

		if (n == 0)
		{
			return 0;
		}

		vector<int>v(n);

		for (int i = 0; i < n; ++i)
		{
			cin >> v[i];
		}

		sort(v.begin(), v.end());

		//조합 실시!

		combi(v, 0);
		cout << endl;
	}
	


	

}

첫번재 풀이

-> 틀림.
왜냐하면, 2번째 테스트 케이스 때문에 next_permutation으로
돌리기에는 무리가 있음.

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


// 03: 26
int main() 
{
	while (1)
	{
		int n;
		cin >> n;

		if (n == 0)
		{
			return 0;
		}
		vector<int>v(n);

		for (int i = 0; i < n; ++i)
		{
			cin >> v[i];
		}

		sort(v.begin(), v.end());

		// 조합 처리
		do
		{
			vector<int>temp(6);
			bool check = false;
			for (int i = 0; i < 6 - 1; ++i)
			{
				if (v[i] > v[i + 1])
				{
					check = true;
					break;
				}
				else
				{
					temp[i] = v[i];
				}
				//cout << v[i] << " ";
			}
			if (check == false)
			{
				temp[6 - 1] = v[6 -1];
				for (auto iter : temp)
					cout << iter << " ";
				cout << endl;
			}
			
			//cout << endl;
			//temp.clear();
		} while (next_permutation(v.begin(), v.end()));

		cout << endl;
	}
	

}