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

🔗 문제

14889번: 스타트와 링크

14889번: 스타트와 링크

 

🖍 풀이

 

어떻게 모든 경우의 수를 돌도록 함수를 짤지 고민만 하면 풀 수 있다.

 

이 문제에서는 팀원을 반으로 갈라야 한다. N이 6명이면 3명의 모일 수 있는 모든 조합을 구해야한다.

그렇다면 팀원을 N/2명 모일 때까지 재귀함수를 호출하도록 작성해준다.

N/2명이 모이면 능력치 차이를 구하고 다시 되돌아가 조합하지 않았던 팀원에 접근한다.

 

1. 팀원을 한명씩 모은다.
   1. 팀원이 다 모였다.
      1. 능력치 계산을 하고 2번으로 간다.
   2. 팀원이 다 모일 때까지 반복
2. 맨 마지막에 넣었던 팀원을 빼고 그 다음 팀원을 넣는다.
   1. (예시) 1, 2, 3 탐색 후 1, 2, 4 탐색
3. 반복문에 int i=idx 조건을 달아 중복 조합을 피할 수 있다.
   1. (예시) (1,2,4)나 (1, 4, 2)는 같은 팀으로 또 탐색할 필요가 없다.  

 

void solve(int depth, int idx) // 팀원 수, 다음 탐색 시작할 인덱스
{
    // 팀 다 모았다. 
    if(depth == N/2)
    {
        // (능력치 구하기)
        return;
    }
		
    //팀원이 부족하다.
    for(int i=idx; i<N; ++i) // i = idx부터 시작해 중복 조합 제거
    {
        if(!teamed[i])
        {
            teamed[i] = true;
            solve(depth+1, i+1); // 팀원을 하나 추가해주고, 마지막으로 넣은 팀원 다음부터 탐색
            teamed[i] = false;
        }
    }
    
    return ;
}

 

채점 결과를 보니 30ms 이하 시간으로 푼 사람들이 있습니다. 

그런 풀이 방법을 아시는 분은 댓글로 공유 부탁드려요.

 

 

💾  소스

#include <iostream>
#include <algorithm>
#include <cmath>
#include <vector>
const int MAX = 21;

int N;
int ability[MAX][MAX];
bool teamed[MAX];
int answer = 1e9;

void solve(int depth, int idx)
{
    if(depth == N/2)
    {
        int start=0, link=0;
        std::vector<int> starts;
        std::vector<int> links;
        
        for(int i=0; i<N; ++i)
        {
            if(teamed[i])
                starts.push_back(i);
            else
                links.push_back(i);
        }
        
        for(int i=0; i<N/2; ++i)
        {
            for(int j=i+1; j<N/2; ++j)
            {
                start += ability[starts[i]][starts[j]] + ability[starts[j]][starts[i]];
                link += ability[links[i]][links[j]] + ability [links[j]][links[i]];
            }
        }
        //std::cout << "start / link : " << start << " / " << link << std::endl;

        answer = std::min(answer, std::abs(start - link));
        return;
    }

    for(int i=idx; i<N; ++i)
    {
        if(!teamed[i])
        {
            teamed[i] = true;
            solve(depth+1, i);
            teamed[i] = false;
        }
    }
    
    return ;
}

int main()
{
    std::cin >> N;
    for(int i=0; i<N; ++i)
        for(int j=0; j<N; ++j)
            std::cin >> ability[i][j];
    
    solve(0, 0);
    
    std::cout << answer;
    
    return 0;
}