https://www.acmicpc.net/problem/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가 주어졌을 때, 수를 고르는 모든 방법을 구하는 프로그램을 작성하시오.접근
백트래킹을 사용해 재귀로 집합 S에 있는 수 중 6개를 뽑아내 중복되는 수 없이 수열을 만들어낸다.
재귀 함수인 Lotto에 인자로 인덱스인 idx와 뽑은 수의 개수, 결과 수열의 자릿수(혹은 크기)를 뜻하는 size를 가진다.
재귀의 탈출 조건으로 size가 6이상일 때, 즉 6개의 수 이상을 뽑게 되면, 결과 벡터에 저장했던 수(뽑은 로또 번호들)를 출력하고 재귀를 종료한다.
6미만이면 번호를 뽑아야한다.
들어온 idx 인덱스에 해당하는 lotto벡터의 값부터 시작해서 뽑는다. size는 자릿수를 나타내므로 rst결과 벡터의 size번째 자리에 뽑은 값을 저장한다.
이렇게 해야 예를들어 rst(2)인 0부터시작하므로 3번째 자리에 lotto(1)~ lotto(k)까지의 경우가 다 올 수 있다.
이제 해당 지리에 해당하는 번호를 뽑았으면
다음 자리를 뽑기위해 뽑았던 수 또 뽑기를 방지하기 위해 i+1로 다음 수열에 있는 수들 만 고려해주도록 한다.
그리고 자릿수도 늘어나므로 size+1해준다.
문제해결
> 재귀함수 Lotto에 입력받은 lotto벡터에 접근하기 위한 인덱스를 idx로 받는다. size로는 로또 번호의 개수를 나타낸다.
> 탈출 조건으로 0부터 시작하므로 6이상부터는 7자리가 되므로 이때 걸리게 해준다.
> 지금 까지 rst에 저장됐던 수들을 출력하고 재귀를 깨준다.
> 6자리의 번호를 채우기위해 입력받은 idx부터 집합 s의 개수인 k개 까지 반복한다.
> 예를 들어 2번째 자리에 대해선 1,2 1,3 1,4 이런식으로 중복되지 않게 따져진다.
> 다음 재귀로 i+1을 줘야 1,1 이나 2,1같은 중복된 경우가 발생하지 않는다.
> main함수에서 0이 입력으로 들어올 때까지 반복해주며 lotto벡터에 집합 s에 대한 수들을 입력받고 이 S의 0번째 인덱스부터 0번째 자리에서부터 채워 가기 위해
Lotto메소드를 호출한다.코드
#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
int k;
vector<int> rst;
vector<int> lotto;
void Lotto(int idx, int size)
{
if (size >= 6)
{
for (int i = 0; i < 6; i++)
cout << rst[i] << " ";
cout << '\n';
return;
}
for (int i = idx; i < k; i++)
{
rst[size] = lotto[i];
Lotto(i + 1, size + 1);
}
}
int main()
{
ios::sync_with_stdio(false);
cin.tie(nullptr);
cout.tie(nullptr);
while (cin >> k && k != 0)
{
lotto.resize(k);
for (int i = 0; i < k; i++) cin >> lotto[i];
rst.resize(k);
Lotto(0, 0);
cout << '\n';
}
}
후기
수를 뽑는 부분에서 rst(idx)로 주었더니 수가 오름차순이 아니고 이상하게 섞여서 나왔다. 그래서 흐름을 써가며 따라가 보니 예를 들어 Lotto(1,2)에 대해서
지금 뽑은 수가 1,2 까지 왔을 때, 다음 재귀에서 Lotto(2,3)으로 넘어가 rst(2) = lott(2)부터 시작하므로 잘 되는 것 처럼 보인다. 하지만 Lotto(2,3)에 대해 다 끝나고 다시 Lotto(1,2)로 돌아오면 i가 증가해서 Lotto(3,3)으로 들어간다. 이때 rst(3) = lotto(3)부터 시작하므로 rst의 2번 인덱스 값에 대한 건데 3번인덱스에 대해 따지고 있는것이다. 그래서 rst(2)에 대한 값을 구해야하는데 재귀가 깨지고 돌아올 때마다 rst(3), rst(4)로 이상한 결과로 접근하고있는것이다.
따라서 rst(idx)의 idx자리가 rst벡터의 특정 자릿수에 대한 값을 구하려는 것이라는 걸 다시 깨닫고 rst(size)로 넣어줬더니 맞았다.
