[BOJ/백준] 14889 스타트와 링크

● [문제번호 14889] 스타트와 링크

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

14889번: 스타트와 링크

 

● 알아야 할 것

: DFS

: 재귀

 

 

● 풀이 과정

: [530 - 브루트 포스 - 재귀] 문제집에 있는 동일한 문제

 

: DFS의 기본 구현 형식에서 크게 벗어나지 않지만,

{N/2 명 까지 선택} + {조합} 을 고려하여 구현하면 된다.

 

: bool로 이루어진 team이라는 1차원 배열을 만들어

각 사람(index)이 스타트 팀(true)인지 링크 팀(false)인지를

구분한다.

 

: 팀의 능력치를 구할 때는

team 배열에서 해당 팀원(row)를 찾고

그 선수의 능력치행(S[row]) 에서

team 배열의 같은 팀원(S[row][col]) 을 찾으면 된다.

 

● 주의 할 것

: 각 배열의 index를 입력할 때 주의한다.

 

: 팀원 능력치를 구하는 부분에서 반복문, 조건문, index들이 혼란스러울 수 있으니 주의한다.

 

 

● 참고 할 것

: NULL

 

 

● 풀이 코드

#include <bits/stdc++.h>

using namespace std;

// S : 능력치
// team : 1 ~ N 범위에서 index가 (true = 스타트 팀 / false = 링크 팀)
int S[21][21];
bool team[21];
int N, sol = 10000;

// 팀 만들기
void makeTeam(int index)
{
    // N / 2 까지 되었는지 확인
    int cnt = 0;
    for(int i = 1; i <= N; i++)
        if(team[i])
            cnt++;
    
    // N / 2명씩 두 팀으로 나눈 경우
    if(cnt == N / 2)
    {
        // 각 팀의 능력치 저장
        int startTeam = 0;
        int linkTeam = 0;
        
        for(int row = 1; row <= N; row++)
        {
            // team의 값이 (true = 스타트 팀 / false = 링크 팀)
            if(team[row])
            {
                for(int col = 1; col <= N; col++)
                    if(team[col])
                        startTeam += S[row][col];
            }
            else
            {
                for(int col = 1; col <= N; col++)
                    if(!team[col])
                        linkTeam += S[row][col];
            }
        }
        
        // 스타트 팀과 링크 팀의 능력치의 차이가 최솟값으로 만들기
        if(abs(startTeam - linkTeam) < sol)
            sol = abs(startTeam - linkTeam);
        
        return ;    
    }
    
    // 각 사람들을 순서대로 조합을 만듬
    for(int i = index + 1; i <= N; i++)
    {
        // 스타트 팀에 들어있지 않은 경우
        if(!team[i])
        {
            // 1. 스타트 팀에 보내기
            // 2. 재귀
            // 3. 스타트 팀에서 빼기 (= 링크 팀으로 보내기)
            team[i] = true;
            makeTeam(i);
            team[i] = false;
        }
    }
}

int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    
    cin >> N;
    
    // 능력치 입력
    for(int a = 1; a <= N; a++)
        for(int b = 1; b <= N; b++)
            cin >> S[a][b];
    
    // 스타트 팀에 0명이기에 (팀을 나누지 않았기에)
    makeTeam(0);
    
    cout << sol;
    
    return 0;
}

 

 

● [백준] - [알고리즘 중급 1/3] - [521 - 브루트 포스 - 순열 (연습)] 문제집

번호	문제 번호	문제 이름	풀이 링크
1	2529	부등호	https://pirateturtle.tistory.com/294
2	1339	단어 수학	https://pirateturtle.tistory.com/295
3	14888	연산자 끼워넣기	https://pirateturtle.tistory.com/296
4	14889	스타트와 링크	https://pirateturtle.tistory.com/297