[Algorithm] 3주차 스터디 - 브루트포스&백트래킹(백준 14889, 1182, 14888, 9663)

A - 백준 14889번 스타트와 링크
https://www.acmicpc.net/problem/14889

14889번: 스타트와 링크

* 문제
오늘은 스타트링크에 다니는 사람들이 모여서 축구를 해보려고 한다. 축구는 평일 오후에 하고 의무 참석도 아니다. 축구를 하기 위해 모인 사람은 총 N명이고 신기하게도 N은 짝수이다. 이제 N/2명으로 이루어진 스타트 팀과 링크 팀으로 사람들을 나눠야 한다.

축구를 재미있게 하기 위해서 스타트 팀의 능력치와 링크 팀의 능력치의 차이를 최소로 하려고 한다. 위의 예제와 같은 경우에는 1, 4번이 스타트 팀, 2, 3번 팀이 링크 팀에 속하면 스타트 팀의 능력치는 6, 링크 팀의 능력치는 6이 되어서 차이가 0이 되고 이 값이 최소이다.

* 코드

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

int n;
int team[20][20];
int check[20];
int ans = 0x7f7f7f7f; //초기화

int getStat(vector<int> oneTeam){
    int stat = 0;
    int size = oneTeam.size();
    for(int i=0; i<size; i++){
        for(int j=0; j<size; j++){
            if(i!=j){
                stat += team[oneTeam[i]][oneTeam[j]];
            }
        }
    }
    return stat;
}   

void backTracking(int depth, int index){
    if(depth == n/2) {
        vector<int> aTeam;
        vector<int> bTeam;
        for(int i=0; i<n; i++) {
            if(check[i]) aTeam.push_back(i);
            else bTeam.push_back(i);
        }
        
        int aStat = getStat(aTeam);
        int bStat = getStat(bTeam);
        ans = min(ans,abs(aStat - bStat));
        return;
    }

    for(int i=index; i<n; i++){
        if(check[i]) continue;
        check[i] = 1;
        backTracking(depth+1,i+1);
        check[i] = 0;
    }
}

int main(){
    cin >> n;
    for(int i=0; i<n; i++)
        for(int j=0; j<n; j++) 
            cin >> team[i][j];
    
    backTracking(0, 0);
    cout << ans << '\n';
}

* 문제 풀이
두 팀의 능력치를 구하고, 그 차이의 최솟값을 구하는 문제이다. 
백트레킹으로 N명을 N/2명으로 나누어 각각 두 팀으로 나눠서 vector에 push해준다.
각각의 능력치를 return하는 getStat 함수를 통해 능력치를 계산하였다.
답은 두 팀 능력치 차이의 최솟값이다.

 

B - 백준 1182번 부분수열의 합
https://www.acmicpc.net/problem/1182

1182번: 부분수열의 합

* 문제
N개의 정수로 이루어진 수열이 있을 때, 크기가 양수인 부분수열 중에서 그 수열의 원소를 다 더한 값이 S가 되는 경우의 수를 구하는 프로그램을 작성하시오.

* 코드

#include <iostream>
using namespace std;

int arr[21];
int N, S, cnt=0;

void backTracking(int start, int sum) {
	if (start >= N) return;
	int tmp = sum;
	tmp += arr[start];
	if (tmp == S) cnt++;
	for (int i=start+1; i<N; i++){
		backTracking(i, tmp);
	}
}

int main() {
	ios::sync_with_stdio(false); 
	cin.tie(NULL);
    
	int tmp;
	cin >> N >> S; 
	for (int i=0; i<N; i++){
	    cin >> arr[i];
	}
	for (int i=0; i<N; i++) {
		tmp = 0;
		backTracking(i, tmp);
	}
    cout << cnt;
}

* 문제 풀이
수 하나를 더할 때 마다 답이 아니면 처음부터 진행하는 것이 아닌, 그 수를 빼고 다른 수를 더해 확인하는 백트래킹 방식을 사용하여 재귀함수 형식으로 문제를 풀이한다.
주의할 점은 sum이 해당하는 값에 도달하더라도 뒤의 것을 계속해서 탐색해야한다는 것이다.

 

C - 백준 14888번 연산자 끼워넣기
https://www.acmicpc.net/problem/14888

14888번: 연산자 끼워넣기

* 문제
N개의 수로 이루어진 수열 A1, A2, ..., AN이 주어진다. 또, 수와 수 사이에 끼워넣을 수 있는 N-1개의 연산자가 주어진다. 연산자는 덧셈(+), 뺄셈(-), 곱셈(×), 나눗셈(÷)으로만 이루어져 있다.
우리는 수와 수 사이에 연산자를 하나씩 넣어서, 수식을 하나 만들 수 있다. 이때, 주어진 수의 순서를 바꾸면 안 된다.
N개의 수와 N-1개의 연산자가 주어졌을 때, 만들 수 있는 식의 결과가 최대인 것과 최소인 것을 구하는 프로그램을 작성하시오.

* 코드

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

int N;
int number[12];
int operators[4];
int maxNum = INT32_MIN;
int minNum = INT32_MAX;

void Calculator(int plus, int minus, int mul, int div, int count, int sum) {
	if (count == N) {
		maxNum = max(maxNum, sum);
		minNum = min(minNum, sum);
	}

	if (plus>0){
	    Calculator(plus-1, minus, mul, div, count+1, sum+number[count]);
	} 
	if (minus>0){
	    Calculator(plus, minus-1, mul, div, count+1, sum-number[count]);
	}
	if (mul>0){
	    Calculator(plus, minus, mul-1, div, count+1, sum*number[count]);
	} 
	if (div>0){
	    Calculator(plus, minus, mul, div-1, count+1, sum/number[count]);
	}
}

int main(void) {
	ios::sync_with_stdio(false); 
	cin.tie(NULL);

	cin >> N;
	for (int i=0; i<N; i ++) {
		cin >> number[i];
	}
	for (int i=0; i<4; i++) {
		cin >> operators[i];
	}
	Calculator(operators[0], operators[1], operators[2], operators[3], 1, number[0]);

	cout << maxNum << '\n' << minNum;
}

* 문제 풀이
계산 가능한 모든 경우의 수를 완전 탐색으로 계산하여 풀이하면 된다.
연산자의 우선 순위같은 것이 없고, 그냥 앞에서 뒤로 차례로 모든 연산자마다의 값을 max와 min으로 계산한다.

 

D - 백준 9663번 N-Queen   
https://www.acmicpc.net/problem/9663

9663번: N-Queen

* 문제
N-Queen 문제는 크기가 N × N인 체스판 위에 퀸 N개를 서로 공격할 수 없게 놓는 문제이다.
N이 주어졌을 때, 퀸을 놓는 방법의 수를 구하는 프로그램을 작성하시오.

* 코드

#include<iostream>
using namespace std;

int N;
int cnt=0;
bool isUsed1[40]; //같은 열에 퀸 존재 여부
bool isUsed2[40]; //우상 대각선에 퀸 존재 여부
bool isUsed3[40]; //좌상 대각선에 퀸 존재 여부

void Queen(int level){
    if(level==N){
        cnt++;
        return;
    }
    for(int i=0; i<N; i++){
        if(isUsed1[i] || isUsed2[i+level] || isUsed3[level-i+N-1]) continue;
        isUsed1[i] = true;
        isUsed2[i+level] = true;
        isUsed3[level-i+N-1] = true;
        
        Queen(level+1);
        isUsed1[i] = false;
        isUsed2[i+level] = false;
        isUsed3[level-i+N-1] = false;
    }
}

int main(void) {
	ios::sync_with_stdio(false); 
	cin.tie(NULL);

	cin >> N;
	Queen(0);
	cout << cnt;
}

* 문제 풀이
체스에서 queen의 특성은 거리와 상관없이 모든 방향으로 움직일 수 있다.
n*n 정사각형 안에 n개의 queen을 배치하는 문제로, queen들은 자신의 일직선상 및 대각선상에 아무 것도 놓이면 안된다.
Queen함수에서는 각각 단계별로 퀸이 존재할 수 있는 여부를 확인한다.
isUsed1는 같은 열에 퀸이 존재하는지, isUsed2는 우상대각선에 퀸이 존재하는지, isUsed3는 좌상대각선에 퀸이 존재하는지 확인한다. (가로의 인덱스가 i, 세로의 인덱스가 j일때 우상대각선은 i+j가 모두 일치, 좌상대각선은 i-j=0이다.)
만약 (level, i)에 퀸을 둘 수 없다면 isUsed1, isUsed2, isUsed3를 모두 true로 변경하고 Queen(level+1)을 호출한다.