[S2] 백준 6603번 로또 C++ 백트래킹

리뷰

 

https://www.acmicpc.net/problem/6603

최대 k개의 순열에서 6개의 숫자를 조합할 수 있는 모든 경우의수를 구하는 문제

 

 

전역 변수

• N : 배열의 최대 크기를 정의할 상수 변수
• k : 각 테스트케이스마다 주어지는 배열의 크기를 저장할 변수
• s : 배열의 원소를 저장할 배열
• c : 선택한 원소의 인덱스를 저장할 벡터

 

함수

1. print

void print() {
	for (int i = 0; i < 6; ++i) {
		cout << s[c[i]];
		if (i != 5) cout << " ";
	}
	cout << "\n";
}

 

선택된 조합을 출력하기 위한 함수

 

2. bt

void bt(int select, int idx) {
	if (select > 6) return;
	if (idx == k) {
		if (select == 6) print();
		return;
	}

	c.push_back(idx);
	bt(select + 1, idx + 1);
	c.pop_back();

	bt(select, idx + 1);
}

 

백트래킹을 통해 조합할 수 있는 모든 경우의 수를 선택하기 위한 함수

 

 

문제풀이

1. while루프를 수행해 매번 k값을 입력받는다. k가 0으로 주어질 경우 break처리한다.
2. k개의 원소를 입력받아 s배열에 저장하여 초기화한다.
3. bt함수에 매개변수 0, 0을 전달하여 호출한다.
4. bt함수 내부에선 변수 select, idx에 각각의 매개변수를 전달받아 저장한다.
5. 첫 번째 기저 조건으로 select가 6보다 클 경우 6개 이상의 수가 선택된 것이므로 리턴처리한다.
6. 두 번째 기저 조건으로 idx가 k일때 select가 6일 경우 print()함수를 호출해 현재 조합을 출력한다.
7. select의 개수와 상관 없이 이후 리턴처리해준다.
8. 기저 조건에 해당하지 않을 경우 c에 idx를 push하고, select, idx를 증가시켜 재귀호출 후 원상복구 시켜준다.
9. select를 그대로, idx를 증가시켜 재귀호출해준다.
10. bt함수가 종료된 후 개행문자를 삽입하여 줄바꿈을 수행해준다.

 

트러블 슈팅

없음

 

 

참고 사항

1. S의 원소는 오름차순으로 주어진다. 따라서 정렬작업을 수행하지 않아도 자동으로 사전 순으로 출력된다.
2. 원소 사이 공백 출력 시 맨 마지막 요소 뒤에는 공백을 추가하지 않아야 출력 형식이 맞는 것 같다.
3. 남은 원소를 모두 추가해도 select가 6보다 작을 경우는 가지치기를 추가로 해줄 수 있다.

 

정답 코드

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

const int N = 14;
int k;
int s[N];
vector<int> c;

void print() {
	for (int i = 0; i < 6; ++i) {
		cout << s[c[i]];
		if (i != 5) cout << " ";
	}
	cout << "\n";
}

void bt(int select, int idx) {
	if (select > 6) return;
	if (idx == k) {
		if (select == 6) print();
		return;
	}

	c.push_back(idx);
	bt(select + 1, idx + 1);
	c.pop_back();

	bt(select, idx + 1);
}

int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);

	while (cin >> k) {
		if (!k) break;
		for (int i = 0; i < k; ++i) cin >> s[i];
		bt(0, 0);
		cout << "\n";
	}
}