[완전 탐색 + 백트래킹] 백준 문제 풀이 - 6603 로또

👩🏻‍💻 문제링크

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

6603번: 로또

 

✍️ 아이디어

 

0. 문제 이해 = k개의 수에서 6개를 골라 순서를 나열 

1. 처음 아이디어가 잘못 떠올라서 강의 봄

처음 아이디어 : 입력받은 앞 숫자를 고정하고 뒤에 수만 next_permutation으로 순서 바꾸려고 했음 , for문으로 순서 바꿀 곳 한자리씩 늘려감 = too 복잡함

2. 선택의 문제이므로 선택하면 0, 선택 안하면 1을 따로 백트래킹할 배열에 저장하는것이 강의 아이디어

 

✍️소스코드

• 내 코드 (강의 코드랑 똑같음)

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

int main()
{
	while(1)
	{
		int k; cin>>k;
		if(k==0) break;
		int arr[k]; int check[k] ={0,}; // 0= 선택한것 1= 선택 안한것
		for(int i=0; i<k; i++)
			cin>>arr[i];
		for(int i=6; i<k; i++)
			check[i]=1; //check 배열 default를 0000001111111...로 만들어줌
		while(1)
		{
			for(int i=0; i<k; i++)
			{
				if(check[i]==0)//수가 선택 되었으면 출력
					cout<<arr[i]<<" ";
			}
			cout<<"\n";
			if(!next_permutation(check,check+k)) break; //다른 수를 선택
		}
		cout<<"\n";
	}
}

 

• 다른 사람의 코드 (재귀 이용)

#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) {//6개 로또가 만들어지면 출력
		for (int i = 0; i < 6; i++) {
			cout << lotto[i] << " ";
		}
		cout << endl;
		return; //5개일때로 반환
	}
	//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;
	}
}

 

체감난이도	걸린시간	참고	사용 문법
하(아이디어 알면 매우 쉬움)	25min	강의	완전탐색(순열), 백트래킹