on my way
[GDSC Week3-1] 백준 1489번:: 스타트와 링크 (C++) 본문
반응형
* 생각한 아이디어 및 문제 풀이
두 팀의 능력치를 구하고, 그 차이의 최솟값을 구하는 문제이다.
백트레킹으로 N명을 N/2명으로 나누어 각각 두 팀으로 나눠서 vector에 push해준다.
각각의 능력치를 return하는 getStat 함수를 통해 능력치를 계산하였다.
답은 두 팀 능력치 차이의 최솟값이다.
* 코드
#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';
}
* 회고
* 문제 링크 : https://www.acmicpc.net/problem/14889
https://codecollector.tistory.com/776
반응형
'algorithm > C++' 카테고리의 다른 글
[GDSC Week3-3] 백준 14888번:: 연산자 끼워넣기 (C++) (0) | 2021.10.24 |
---|---|
[GDSC Week3-2] 백준 1182번:: 부분수열의 합 (C++) (0) | 2021.10.24 |
[GDSC Week2-4] 백준 3078번:: 좋은친구 (C++) (0) | 2021.10.11 |
[GDSC Week2-3] 백준 2346번:: 풍선 터뜨리기 (C++) (0) | 2021.10.11 |
[GDSC Week2-2] 백준 10828번:: 스택 (C++) (0) | 2021.10.11 |