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
www.acmicpc.net
알고리즘은 다음의 순서로 진행된다.
1. 첫번째 수(k)와 k개의 숫자를 입력 받아 배열에 담는다 ( k==0 일 때 종료)
2. 입력받은 배열을 가지고 6개 숫자를 뽑는 조합을 사전 순으로 출력한다.
---> 단, 숫자를 오름차순으로 입력받으므로 별도의 정렬은 하지 않아도 된다.
---> 순서만 다른 숫자조합까지 출력하지 않도록 주의해야한다.
|
#include <iostream>
#include <vector>
using namespace std;
vector<int> numArr;
vector<int> picked;
vector<bool> visited;
void Solution(vector<int>& picked,int toPick)
{
if (toPick == 6) // 기저사례. 6개 숫자 뽑았으면 출력
{
for (int i = 0; i < 6; i++)
cout << picked[i] << ' ';
cout << '\n';
return;
}
int len = numArr.size();
for (int i = 0; i < len; i++)
{
if (!picked.empty())
if (picked.back() > numArr[i]) continue;
if (visited[i] == true) continue;
visited[i] = true;
picked.push_back(numArr[i]);
Solution(picked, toPick + 1);
visited[i] = false;
picked.pop_back();
}
}
int main(void)
{
int num;
while (1)
{
cin >> num;
if (num == 0) break;
for (int i = 0; i < num; i++)
{
int n;
cin >> n;
numArr.push_back(n);
visited.push_back(false);
}
Solution(picked, 0);
cout << '\n';
numArr.clear();
visited.clear();
}
return 0;
}
http://colorscripter.com/info#e" target="_blank" style="color:#4f4f4ftext-decoration:none">Colored by Color Scripter
|
알고리즘 200일 프로젝트 - 7day
내일도 열심히!
'알고리즘 > BOJ' 카테고리의 다른 글
| 백준 1966번: 프린터 큐 (0) | 2020.04.13 |
|---|---|
| 백준 14888번: 연산자 끼워넣기 (0) | 2020.04.12 |
| 백준 7568번: 덩치 (0) | 2020.04.11 |
| 백준 14502번: 연구소 (0) | 2020.04.11 |
| 백준 2231번: 분해합 (0) | 2020.04.11 |
