[백준/C++]14889번_ 스타트와 링크

최근에 너무 바빴어서 열심히 백준을 업로드하지 못했습니다.
다시 정신을 차리려 했지만 과제가 너무 많고, 이제 곧 중간고사더라고요.
그래도 하는 데 까지 최선을 다해서 열심히 풀어보겠습니다!

문제는 다음과 같습니다.
이 문제는 참고로 삼성 SW 역량 테스트 기출 문제에 나왔던 문제라고 합니다.

⭐️문제의 핵심 포인트는 다음과 같습니다.⭐️

1. 두 그룹으로 나누기 (분할)
2. 각각 그룹의 능력치 구하기

💡먼저 저는 입력을 2차원 배열에다가 저장하였고,

💡dfs를 이용하여 두 그룹으로 분할하였습니다.
(두 그룹에 대한 정보는 각각 배열 res와 벡터 tmp에 담아두었습니다.)

💡그리고 이중 for문을 돌면서 각각 그룹의 능력치를 계산한 후, 더 작은 값을 계속해서 변수 gap에 갱신해주었습니다.

처음 짰던 전체 코드는 다음과 같습니다.

#include <bits/stdc++.h>
using namespace std;

int n;
int res[21]={0, };
int a[20][20]={0, };
vector<int> v;

int total = 0;
int gap = INT_MAX;

void dfs(int cnt){
    if(cnt==n/2 + 1){
        vector<int> tmp = v;
        for(int i=1; i<=n/2; i++){
            tmp.erase(remove(tmp.begin(), tmp.end(), res[i]), tmp.end()); // 원소 지우기
        }

        int sum = 0, sum2 = 0;

        for(int i=1; i<=n/2; i++){
            for(int j=1; j<=n/2; j++){
                sum += a[res[i]][res[j]]; // 그룹1 능력치
                sum2 += a[tmp[i-1]][tmp[j-1]]; // 그룹2 능력치
            }
        }
        
        // 최솟값 갱신시키기
        gap = min(gap, abs(sum-sum2));
    }
    else{
        for(int i=res[cnt-1]+1; i<n; i++){
            res[cnt]=i;
            dfs(cnt+1);
            res[cnt]=0;
        }
    }
}

int main(){
  ios_base::sync_with_stdio(false);
  cin.tie(nullptr);
  cout.tie(nullptr);

  cin>>n;
  for(int i=0; i<n; i++){
      for(int j=0; j<n; j++){
          cin>>a[i][j]; // 2차원 배열 입력받기
          total += a[i][j];
      }
      v.emplace_back(i);
  }
  res[0]=-1;
  dfs(1);

  cout<<gap<<"\n";
  return 0;
}

이 코드는 모든 분할의 과정을 수행합니다.
하지만 다시 생각해보니, 분할의 과정은 절반만 수행해도 됩니다.

0, 1 / 2, 3 이나
2, 3 / 0, 1 의 분할은 동일하기 때문입니다.

그래서 아예 그룹 하나에 특정 원소를 고정시켜, 시간을 단축하려 했습니다.

  res[1]=0;
  dfs(2);

이것만 고쳐 개선한 최종 풀이는 다음과 같습니다.🙆🏻‍♀️

#include <bits/stdc++.h>
using namespace std;

int n;
int res[21]={0, };
int a[20][20]={0, };
vector<int> v;

int total = 0;
int gap = INT_MAX;

void dfs(int cnt){
    if(cnt==n/2 + 1){
        vector<int> tmp = v;
        for(int i=1; i<=n/2; i++){
            tmp.erase(remove(tmp.begin(), tmp.end(), res[i]), tmp.end()); // 원소 지우기
        }

        int sum = 0, sum2 = 0;

        for(int i=1; i<=n/2; i++){
            for(int j=1; j<=n/2; j++){
                sum += a[res[i]][res[j]]; // 그룹1 능력치
                sum2 += a[tmp[i-1]][tmp[j-1]]; // 그룹2 능력치
            }
        }
        
        // 최솟값 갱신시키기
        gap = min(gap, abs(sum-sum2));
    }
    else{
        for(int i=res[cnt-1]+1; i<n; i++){
            res[cnt]=i;
            dfs(cnt+1);
            res[cnt]=0;
        }
    }
}

int main(){
  ios_base::sync_with_stdio(false);
  cin.tie(nullptr);
  cout.tie(nullptr);

  cin>>n;
  for(int i=0; i<n; i++){
      for(int j=0; j<n; j++){
          cin>>a[i][j]; // 2차원 배열 입력받기
          total += a[i][j];
      }
      v.emplace_back(i);
  }
  res[1]=0; // 그룹에 특정 멤버 고정시키기 -> 1/2로 분할 줄이기
  dfs(2);

  cout<<gap<<"\n";
  return 0;
}

실제로 시간이 개선되는지 확인해보았습니다.

60ms -> 32ms

정말 절반이 줄어든 것을 확인할 수 있습니다✅