[C++][백준] 6603번 로또 :: seoftware

 

 

 

---

 

소스코드

---

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

int S[13];
int lotto[6];
int k;
//start는 S의 인덱스, depth는 lotto의 인덱스 
void getCombi(int start, int depth) {
	if (depth == 6) {
		for (int i = 0; i < 6; i++) {
			cout << lotto[i] << " ";
		}
		cout << endl;
		return;
	}
	//start부터 k-1 까지 순서
	for (int i = start; i < k; i++) {
		lotto[depth] = S[i];
		getCombi(i+1, depth+1);
	}
}
int main(void) {
	while (1) {
		cin >> k;
		if (k == 0) break;
		for (int i = 0; i < k; i++) {
			cin >> S[i];
		}
		getCombi(0, 0);
		cout << endl;
	}
}

 

이해

---

S[] = { 1, 2, 3, 4, 5, 6, 7, 8 } , k = 8 이라고 할 때 위에 몇 가지 경우만 그려보면 다음과 같다.

lotto[0]	lotto[1]	lotto[2]	lotto[3]	lotto[4]	lotto[5]
1	2	3	4	5	6
1	2	3	4	5	7
1	2	3	4	5	8
1	2	3	4	6	7
1	2	3	4	6	8
1	2	3	4	7	8
1	2	3	5	6	7
˙ ˙ ˙

 

getCombi 함수를 살펴보면 인수가 start 와 depth로 나뉘는 걸 볼 수 있다.

start는 S의 인덱스를 가리키고, depth는 말 그대로 깊이인 동시에 lotto의 인덱스를 가리킨다.

getCombi(0, 0) 안의 for문에서 lotto[0] = 1 이 저장되고 다시 getCombi(1, 1)이 호출된다.

getCombi(1, 1) 안의 for문에서 lotto[1] = 2 이 저장되고 다시 getCombi(2, 2)가 호출된다. 

반복적으로 수행된 후, getCombi(5, 5) 안의 for문에서 lotto[5] = 6 이 저장되고 getCombi(6, 6)가 호출된다.

depth 가 6이므로 lotto의 6개 요소들을 출력해주고 return 한다. 

getCombi(6, 6)을 부른 곳이 getCombi(5, 5)의 for문이므로 그곳에서 반복문을 이어간다.

이전에 lotto[5] = S[5] = 6 이었던 것이 i++ 되어서 lotto[5] = S[6] = 7이 된다. 

다음에 다시 돌아왔을 때는 마찬가지로 lotto[5] = S[7] = 8 이 되고,

다시 돌아왔을 때는 i<k 조건에 걸려서 그 전 호출인 getCombi(4, 4)로 돌아간다.

호출과 리턴을 반복하며 답을 출력한다.