[BOJ] 6603 - LOTTO

안녕하세요.

여행벌입니다.

오늘은 대표적인 백트래킹 문제 LOTTO 풀이를 해보겠습니다.

---

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

6603번: 로또

[알고리즘풀이]

1. 백트레킹기법을 이용하여 k개의 수를 고르면 출력을 반복해줍니다.

#include<cstdio>
#include<vector>

using namespace std;

int list[12];

void printPicked(vector<int>& picked) {
	for (int i = 0; i < 6; i++)
		printf("%d ", list[picked[i]]);
	printf("\n");
}

void pick(int ninput, vector<int>& picked, int toPick) {
	if (toPick == 0) {
		printPicked(picked);
		return;
	}
	int smallest = picked.empty() ? 0 : picked.back() + 1;
	for (int next = smallest; next < ninput; next++) {
		picked.push_back(next);
		pick(ninput, picked, toPick - 1);
		picked.pop_back();
	}
}

int main(void) {
	while(1){
		int ninput;
		scanf("%d", &ninput);

		if (ninput == 0) {
			return 0;
		}

		for (int i = 0; i < ninput; i++)
			scanf("%d", &list[i]);

		for (int i = 0; i <= ninput - 6; i++) {
			vector<int> picked;
			picked.push_back(i);
			pick(ninput, picked, 5);
			picked.pop_back();
		}
		printf("\n");
	}
}

---

열심히 공부하고 노력하고 있는 꿈 많은 예비 개발자입니다.

혼자서 공부한 내용을 정리하고 포스팅하다 보니 틀린 내용이 있을 수도 있습니다.

많은 조언과 가르침 주실 분은 댓글로 자유롭게 남겨주셔도 좋을 것 같습니다! 

감사합니다.