https://www.acmicpc.net/problem/6603
6603번: 로또
문제 독일 로또는 {1, 2, ..., 49}에서 수 6개를 고른다. 로또 번호를 선택하는데 사용되는 가장 유명한 전략은 49가지 수 중 k(k>6)개의 수를 골라 집합 S를 만든 다음 그 수만 가지고 번호를 선택하는
www.acmicpc.net
조합 첫번째
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
|
#include <iostream>
#include <vector>
#include <algorithm>
int k = 0;
std::vector<int> vec, lotto;
int ans = 0;
bool input()
{
ans = 0;
int input;
vec.clear();
lotto.clear();
std::cin >> k;
for (int i = 0; i < k; ++i)
{
std::cin >> input;
vec.push_back(input);
}
return k;
}
void solve()
{
lotto = { 0, 0, 0, 0, 0, 0 };
for (int i = 0; i < k - 6; ++i)
{
lotto.push_back(1);
}
//std::sort(lotto.begin(), lotto.end());
do
{
for (int i = 0; i < k; ++i)
{
if (lotto[i] == 0)
{
std::cout << vec[i] << ' ';
}
}
std::cout << '\n';
} while (std::next_permutation(lotto.begin(), lotto.end()));
std::cout << '\n';
}
int main()
{
while (input())
{
solve();
}
return 0;
}
|
cs |
재귀를 쓰지는 않았고, next_permutation 사용했다
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
|
std::vector<int> tmp1 = { 1, 2, 3 };
std::vector<int> tmp2 = { 0, 0, 1 };
do
{
for (auto& it : tmp1)
{
std::cout << it << ' ';
}
std::cout << '\n';
} while (std::next_permutation(tmp1.begin(), tmp1.end()));
std::cout << "-------------------------------------------------\n";
do
{
for (auto& it : tmp2)
{
std::cout << it << ' ';
}
std::cout << '\n';
} while (std::next_permutation(tmp2.begin(), tmp2.end()));
|
cs |
원리는 다음과 같다
같은 숫자가 존재한다면 빼버린다
a b c
0 0 1
b a c
0 0 1
이러한 경우는 한번만 출력
즉
a b
a c
b c
를 출력하면서 3개의 숫자 중 2개의 숫자를 뽑는 조합인 것
결론은 next_permutation을 이용한 조합의 구현.
'알고리즘' 카테고리의 다른 글
| koi : 연구활동 가는 길(L) (0) | 2020.06.26 |
|---|---|
| koi : 저울 추(L) (0) | 2020.06.26 |
| 백준 14888 : 연산자 끼워넣기 (0) | 2020.06.23 |
| 백준 14502 : 연구소 (브루트포스) (0) | 2020.06.19 |
| 백준 17478 : 재귀함수가 뭔가요? (0) | 2020.06.19 |