[문과 코린이의 IT 기록장] C++ 백준 문제풀이[BF] - 로또 (6603)

[문과 코린이의 IT 기록장] C++ 백준 문제풀이[BF] - 로또 (6603)

[문과 코린이의 IT 기록장] C++ 백준 문제풀이[BF] - 로또 (6603)

 

---

 

6603번: 로또

[ 문제 ]

독일 로또는 {1, 2, ..., 49}에서 수 6개를 고른다.

로또 번호를 선택하는데 사용되는 가장 유명한 전략은 49가지 수 중 k(k>6)개의 수를 골라 집합 S를 만든 다음 그 수만 가지고 번호를 선택하는 것이다.

예를 들어, k=8, S={1,2,3,5,8,13,21,34}인 경우 이 집합 S에서 수를 고를 수 있는 경우의 수는 총 28가지이다. ([1,2,3,5,8,13], [1,2,3,5,8,21], [1,2,3,5,8,34], [1,2,3,5,13,21], ..., [3,5,8,13,21,34])

집합 S와 k가 주어졌을 때, 수를 고르는 모든 방법을 구하는 프로그램을 작성하시오.

[ 입력 ]

입력은 여러 개의 테스트 케이스로 이루어져 있다. 각 테스트 케이스는 한 줄로 이루어져 있다. 첫 번째 수는 k (6 < k < 13)이고, 다음 k개 수는 집합 S에 포함되는 수이다. S의 원소는 오름차순으로 주어진다.

입력의 마지막 줄에는 0이 하나 주어진다. 

[ 출력 ]

각 테스트 케이스마다 수를 고르는 모든 방법을 출력한다. 이때, 사전 순으로 출력한다.

각 테스트 케이스 사이에는 빈 줄을 하나 출력한다.

---

[ 코드 ]

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

int main() {
	while (true)
	{
		int k;
		cin >> k;

		if (k == 0)
		{
			break;
		}

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

		/// <summary>
		///  선택 O, 선택 X 구분 (인덱스)
		/// </summary>
		/// <returns></returns>
		vector <int> d;
		for (int i = 0; i < k-6; i++) // 나머지부분 (k개 중 6개)
		{
			d.push_back(0); // 선택 안된 개수만큼 0 입력
		}
		for (int i = 0; i < 6; i++)
		{
			d.push_back(1); // 선택된 개수(6개) 1 입력
		}

		
		/// <summary>
		/// i번째 d[i]가 선택되었다면, push_back(arr[i])값 집어넣기.
		/// </summary>
		/// <returns></returns>
		vector <vector<int>> ans;
		do
		{
			vector <int> current;
			for (int i = 0; i < k; i++)
			{
				if (d[i] == 1)
				{
					current.push_back(arr[i]);
				}
			}
			ans.push_back(current); // ans[i]에 하나의 current 모음 넣기 (하나의 수열)
			

		} while (next_permutation(d.begin(),d.end()));
		// k가 8이라면 00111111 (첫번째) 01111101 (두번째) 이런식으로 바뀌게 됨.
		// 따라서 이 순서대로 선택된 것과 선택 안된 것에 따라, current에 값 입력


		sort(ans.begin(), ans.end());
		// 사전순으로 출력
		// 0부터 입력했기 때문에, 그리고 arr값 입력도 정렬이 안되어있기 때문에, 꼭 오름차순 정렬을 진행해줘야함.

		for (auto& v : ans) {
			// 1번째 ... k번째 ans 돌리기
			for (int i = 0; i < v.size(); i++)
			{
				cout << v[i] << ' ';
			}
			cout << '\n';
		}

		cout << '\n'; 
		// 각 테스트케이스 사이에는 빈 줄을 하나 출력
	}

	return 0;
}