백준 6603 c++ "로또" -PlusUltraCode-

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

 

[필자 사고]

정해진 집합내에서 부분집합을 구해야 하는 문제이다.

또한 정해진 정렬을 기준으로 뽑아야 한다.

필자는 조합을 생각해냈따. 

DFS를 이용하여 백트래킹을 이용하여 해당 알고리즘을 구현했다.

 

아래는 자세한 코드 해설이다.

[코드 해설]

✅ main() 함수

• 무한 루프를 돌면서 사용자로부터 입력을 받는다.
• num이 0이면 종료 (break)
• 아닌 경우 Game_Start(num)를 호출해 num개의 숫자를 입력받고 조합을 계산
• 각 조합 블록 뒤에는 줄바꿈 출력

---

✅ Game_Start(int N) 함수

• 입력받은 숫자 N개를 arr 벡터에 저장하고 오름차순 정렬한다.
• 조합 결과를 담을 result 벡터를 초기화한다.
• DFS(0, 0) 호출 → 인덱스 0부터 시작하며 0개 선택된 상태

---

✅ DFS(int idx, int size) 함수

• 백트래킹을 통해 arr에서 6개의 숫자 조합을 생성
• size == 6이면, result 벡터에 저장된 6개 숫자를 출력하고 리턴
• 그렇지 않으면 idx부터 arr.size()까지 반복하면서:
  • 현재 숫자를 result에 추가
  • 다음 인덱스(i+1)부터 다시 DFS 호출 (중복 방지)
  • 재귀가 끝나면 마지막 요소를 제거 (pop_back) → 백트래킹 핵심

[소스 코드]

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

vector<int> arr;
vector<int> result;

void DFS(int idx,int size) {
	if (size == 6) {
		for (int i = 0; i < 6; i++) {
			cout << result[i] << " ";
		}
		cout << "\n";
		return;
	}

	for (int i = idx; i < arr.size(); i++) {
		result.push_back(arr[i]);
		DFS(i + 1, size + 1);
		result.pop_back();
	}
}

void Game_Start(int N) {
	arr.clear();
	result.clear();
	for (int i = 0; i < N; i++) {
		int num;
		cin >> num;
		arr.push_back(num);
	}
	sort(arr.begin(), arr.end());
	DFS(0, 0);
}

int main(void) {
	while (1) {
		int num;
		cin >> num;
		if (num == 0)break;
		Game_Start(num);
		cout << "\n";
	}
}