[풀이]백준 풀이(XVII/6603 등)

문제풀이

[RE]로또(6603, DFS)

• 로또는 1~49에서 숫자를 6개 고른다.
• 49개 중 K(>6)개를 골라 그 수로 번호를 선택하는 전략이 있다.
• K개를 골랐을 때 나올 수 있는 모든 순열을 구하시오.

회고

• 아주 기본 DFS인데 구현이.. 제대로 안되었다.
• 쉽게생각해라 쉽게쉽게…

#include<iostream>
#define MAX_SIZE 13
using namespace std;
int lotto[MAX_SIZE];
int combi[MAX_SIZE];
int k;

void dfs(int start, int depth) {
    if(depth == 6) {                    //탈출조건
        for(int i=0; i<6; i++) {
            cout << combi[i] << ' ';    //조합하나를 출력한 뒤 탈출
        }
        cout << '\n';
        return;
    }

    for(int i=start; i<k; i++) {    //lotto배열 0부터 k-1까지 탐색함
        combi[depth] = lotto[i];    //depth는 깊이 -> 0~5번째 깊이까지 재귀를통해 새로 탐색한 숫자를 넣음.
        dfs(i+1, depth+1);            //재귀 들어가는 부분 , 하나의 깊이를 탐색 후 저장했으니 다음 함수호출할때는 깊이+1을 해줘야함.
    }
}

int main() {
    while(cin >> k && k) {            //0을 입력 받을 때 까지 무한루프
        for(int i=0; i<k; i++) {
            cin >> lotto[i];
        }
        dfs(0,0);
        cout << '\n';

    }
    return 0;
}

스타트와 링크(14889, 기출)

• 총 N명이 모였다 N/2씩 팀을 두개 이룬다(N=짝수)
• 능력치 S(i,j)는 i번사람과 j번사람이 같은 팀이 되었을 때 팀에 더해지는 능력치이다.

• 팀의 능력치는 S(i,j) + S(j,i) 들의 합이다.

• 두 팀의 능력차이를 최소로하게 팀을 나누고 싶다.
• 4<= N <= 20
• S(i,i) = 0
• S(i,j) <=100

회고

• 디버깅하는데 시간을 너무 많이 쓴다..
• 조합관련된 문제를 풀 때 크게 도움이 될 것 같다.

#include<iostream>
#include<vector>
#include<queue>
#include<algorithm>
#define INF 987654321
using namespace std;

int n,m;
int s[20][20];
int teamA=INF, teamB=INF, aTmp=0, bTmp=0, Answer = INF;
int start[10], link[10];
vector<int> human;
vector<int> helper;

vector<int> synergyA;
vector<int> synergyB;
vector<int> twoA;
vector<int> twoB;


//n명중 n/2를 뽑아서 계산한다?

void calcA(){
	//A팀의 최소값을 구하자
	do{
		int x, y;
		queue<int> tmp;
		for(int i=0; i<m; i++){
			if(twoA[i]==1){
				tmp.push(synergyA[i]);
			}
		}

		while(!tmp.empty()){
			x = tmp.front(); tmp.pop();
			y = tmp.front(); tmp.pop();
			//cout<< "team A is " << x << " " << y << " " << "and synergy is " << s[x][y] << " and " << s[y][x] << endl;
			aTmp += (s[x][y] + s[y][x]);

		}
	}while(next_permutation(twoA.begin(), twoA.end()));
}

void calcB(){
	//B팀의 최소값을 구하자
	do{
		int x, y;
		queue<int> tmp;
		for(int i=0; i<m; i++){
			if(twoB[i]==1){
				tmp.push(synergyB[i]);
			}
		}

		while(!tmp.empty()){
			x = tmp.front(); tmp.pop();
			y = tmp.front(); tmp.pop();
			//cout<< "teamB is " << x << " " << y << " " << "and synergy is " << s[x][y] << " and " << s[y][x] << endl;

			bTmp += (s[x][y] + s[y][x]);
		}
	}while(next_permutation(twoB.begin(), twoB.end()));

}

int main(){
	cin >> n;
	m = n/2;

	for(int i=0; i<m; i++){
		if(i==0 || i==1) {
			twoA.push_back(1);
			twoB.push_back(1);
		}
		else {
			twoA.push_back(0);
			twoB.push_back(0);
		}
	}

	for(int i=0; i<n; i++){
		for(int j=0; j<n; j++){
			cin >> s[i][j];
		}
		human.push_back(i);
		if(i%2==0) helper.push_back(0);
		else helper.push_back(1);
	}

	sort(human.begin(), human.end());
	sort(helper.begin(), helper.end());
	sort(twoA.begin(), twoA.end());
	sort(twoB.begin(), twoB.end());

	//팀을 나누고
	do{
		int idxA = 0;
		int idxB = 0;
		for(int i=0; i<helper.size(); i++){
			if(helper[i] ==1){
				synergyA.push_back(human[i]);
				start[idxA]= human[i];
				idxA++;
			}
			else{
				synergyB.push_back(human[i]);
				link[idxB] = human[i];
				idxB++;
			}
		}

		sort(synergyA.begin(), synergyA.end());
		sort(synergyB.begin(), synergyB.end());

//		cout << "teamA is ";
//		for(int i=0; i<m; i++){
//			cout << synergyA[i] << " ";
//		}
//		cout << endl;

//		cout << "teamB is ";
//		for(int i=0; i<m; i++){
//			cout << synergyB[i] << " ";
//		}
//		cout << endl;

		calcA();
		calcB();

//		cout << "A synergy is " << aTmp << endl;
//		cout << "B synergy is " << bTmp << endl;
		Answer = min(Answer, abs(aTmp-bTmp));

		if(Answer==0) break;
		aTmp = 0;
		bTmp = 0;
		synergyA.clear();
		synergyB.clear();

	}while(next_permutation(helper.begin(), helper.end()));

	cout << Answer;
}