[백준/C++]: 6603번 로또 - backtracking

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

6603번: 로또

---

문제해석

---

 

k개 만큼에 수를 뽑은 후, 그 수들을 가지고 나올 수 있는 모든 경우의 수에서의 6자리 숫자 집합을 생성하여 출력해주는 문제이다.

---

코드

---

 

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

int S[13];
int L[6];
int k;
void solved(int s, int l) {
	if (l == 6) {
		for (int i = 0; i < 6; i++) {
			cout << L[i] << " ";
		}
		cout << endl;
		return;
	}
	
	for (int i = s; i < k; i++) {
		L[l] = S[i];
		solved(i+1, l+1);
	}
}
int main(void) {
	while (1) {
		cin >> k;
		if (k == 0) break;
		for (int i = 0; i < k; i++) {
			cin >> S[i];
		}
		solved(0, 0);
		cout << endl;
	}
}

---

문제풀이

---

s는 S의 인덱스를 가리키고, l은 L의 인덱스를 가리킨다. solved(0, 0) 안의 for문에서 l[0] = 1 이 저장되고 다시 solved(1, 1)이 호출된다. l이 6이므로 L의 6개 요소들이 호출 되고 출력해준 후 return을 하게된다. 

그후, solved(6, 6)을 부른 곳이 solved(5, 5)의 for문이므로 그곳에서 반복문을 이어간다. 이전에 l[5] = S[5] = 6 이었던 것이 i++ 되어 l[5] = S[6] = 7 된다. 이와같이 호출과 리턴을 반복하며 답을 출력한다.