[백준 / BOJ] - 14889번 스타트와 링크 C++ 풀이 (삼성 코딩테스트 기출)

---

 

백준 - 단계별로 풀어보기 [14889] 

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

 

문제

 

 

풀이

 

dfs를 활용한 조합 알고리즘을 사용하여 N명의 사람중 N/2명을 뽑는 조합의 모든 경우의 수를 찾고, 이를 바탕으로 팀을 나눴을 때 두 팀의 능력치의 차이가 가장 최소가 될 때의 값을 저장하여 출력하면 되는 문제이다.

 

자세한 사항은 코드를 직접 보며 이해하자.

 

 

코드

 

#include <cstdio>
#include <vector>
#include <cmath>
using namespace std;

bool team[20] = {};
int score[20][20] = {};
int N, mymin = 99999999;
void teamset(int idx, int cnt)
{
    vector<int> start; // 스타트 팀원의 인덱스값
    vector<int> link; // 링크팀 팀원의 인덱스값
    int start_score = 0;
    int link_score = 0;
    if(cnt == (N/2))
    {
        for(int i = 0; i < N; i++)
        {
            if(team[i] == true) // 선택된 사람들은 start팀에
                start.push_back(i);
            else // 그 외의 사람들은 link팀으로
                link.push_back(i);
        }
        for(int i = 0; i < (N/2); i++)
            for(int j = 0; j < (N/2); j++)
            {
                start_score += score[start[i]][start[j]];
                link_score += score[link[i]][link[j]];
            } // 각 팀의 능력치의 합 계산
        if(abs(start_score - link_score) < mymin)
            mymin = abs(start_score - link_score);
        return;
    }
    for(int i = idx; i < N; i++)
    {
        if(team[i])
            continue;
        else
        {
            team[i] = true;
            teamset(i,cnt+1);
            team[i] = false;
        }
    }
}
int main() {
    scanf("%d",&N);
    for(int i = 0; i < N; i++)
        for(int j = 0; j < N; j++)
            scanf("%d",&score[i][j]);
    teamset(0,0);
    printf("%d",mymin);
}

 

 

평가

 

해당 문제는 단순히 Brute-Force와 비슷한 방식으로 풀게 될 경우, 반드시 시간초과가 발생하기 때문에 조합으로 발생할 수 있는 팀의 경우의 수를 한번씩만 계산하게끔하여 풀이를 진행해야한다.

 

대부분의 오답 사유는 시간초과일 것으로 예상되며, 시간초과가 발생하는 원인은 아마도 백트래킹 알고리즘이 각 조합에 대해서 연산을 단 한번만 하는게 아니라 중복연산이 진행중일 가능성이 높다.