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

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

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

15661번: 링크와 스타트

 

● 알아야 할 것

: DFS

: 재귀

 

● 풀이 과정

: 스타트와 링크 문제에서 팀인원 조건을 수정하면 된다.

 

: 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)
{
    // 1명이라도 S팀에 있는 지 확인
    int cnt = 0;
    for(int i = 1; i <= N; i++)
        if(team[i])
            cnt++;
            
    // 두 팀으로 나눈 경우
    if(0 < cnt < N)
    {
        // 각 팀의 능력치 저장
        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);
    }
    
    // 각 사람들을 순서대로 조합을 만듬
    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;
}

 

 

● [백준] - [알고리즘 기초 2/2] - [530 - 브루트 포스 - 재귀] 문제집

번호	문제 번호	문제 이름	풀이 링크
1	9095	1, 2, 3 더하기	https://pirateturtle.tistory.com/258
2	1759	암호 만들기	https://pirateturtle.tistory.com/259
3	14501	퇴사	https://pirateturtle.tistory.com/260
4	14889	스타트와 링크	https://pirateturtle.tistory.com/261
5	15661	링크와 스타트	https://pirateturtle.tistory.com/262
6	2529	부등호	https://pirateturtle.tistory.com/263
7	1248	맞춰봐	https://pirateturtle.tistory.com/264