이 포스팅은 Algorithm Problem Solving 시리즈 113 편 중 102 번째 글 입니다.
목차
실버2 : 재귀를 통한 완전탐색 문제이다.
단순한 문제였다. 재귀를 통해 만들 수 있는 모든 경우를 출력하면 되는 문제였다. 나 같은 경우 재귀를 통해 들어갈 때, 탐색하지 않아도 되는 부분을 거르는 코드를 작성했다. 아마 다른 분들도 작성했을 것이다.
이 문제에서 고려해야 되는 점은 다음과 같다.
- 어떻게 출력하게 만들 것인가?
- 어느 상황에서 탐색을 하지 않게 가지를 칠 것인가?
출력 방법
checkbox라는 배열을 만들어 깊이가 6이 되었을 때 모두 출력하였다.
백트래킹
이 문제는 간단한 백트레킹이지만, 써보면, 현재 위치에서 나머지 공을 선택할 수 있는 가지수와 지금 부터 선택해야 하는 가지수를 비교했다.
현재 위치로 부터 남은 공의 개수 < 앞으로 선택해야 하는 공의 개수
이와 같은 경우는 탐색이 불가능 하므로 함수를 콜하지 않았다.
Code
// 실버2 : 백준 6603번 로또
#include <iostream>
#include <string>
#include <algorithm>
using namespace std;
const int K = 6;
int arr[14];
bool checkbox[14] = {0};
int N = -1;
void go(int start, int count){
int restOfBallFromStart = N-(start+1);
if (count == 6) {
for (int i = 0; i < N; i++)
if (checkbox[i]) cout << arr[i] << " ";
cout << '\n';
return;
}
for (int i = start+1; i < N; i++) {
if (restOfBallFromStart < K-(count+1)) break;
else {
checkbox[i] = 1;
go(i, count+1);
checkbox[i] = 0;
}
}
}
int main(){
ios_base::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);
while (N != 0) {
fill(&arr[0], &arr[13], 0);
cin >> N;
for (int i = 0; i < N; i++) {
cin >> arr[i];
}
go(-1, 0);
cout << '\n';
}
return 0;
}