[백준/C언어] 14889번 - 스타트와 링크

백준 웹사이트 "14889번 - 스타트와 링크" 문제풀이입니다.

언어는 C언어입니다. (제출 언어: C99)

 

---

문제

14889번: 스타트와 링크

---

소스 코드

#include <stdio.h>
#include <stdlib.h>

void solve(int count);

//global variables
int N;
int abilities[20][20];  //4<=N<=20
int min = 18810;    //최대 20명, 400-20=380 개의 능력치 -> 190*100 - 190*1 = 18810
int all[20];
int max_start = -1; //start 팀의 가장 큰 숫자

int main(void){
    scanf("%d", &N);
    for(int i=0; i<N; i++){
        for(int j=0; j<N; j++){
            scanf("%d", &abilities[i][j]);
        }
        all[i]=0;
    }

    solve(0);
    printf("%d\n", min);
}

void solve(int count){
    if(count == N/2){
        //능력치 합산
        int start[N/2];
        int link[N/2];
        int start_count=0, link_count=0;
        for(int i=0; i<N; i++){
            if(all[i]==1){
                start[start_count]=i;
                start_count++;
            }
            else{
                link[link_count]=i;
                link_count++;
            }
        }

        int start_sum = 0;
        int link_sum = 0;
        for(int i=0; i<N/2; i++){
            for(int j=0; j<N/2; j++){
                start_sum += abilities[start[i]][start[j]];
                link_sum += abilities[link[i]][link[j]];
            }
        }

        //팀 간의 차 계산, 비교
        int diff = abs(start_sum - link_sum);
        //printf("diff: %d\n", diff);
        if(diff < min)
            min = diff;
    }
    else{
        //start 팀에 한 명 배정
        if(count==0){   //항상 '0'이 start팀에 들어가도록 함
            all[0]=1;
            max_start=0;
            //재귀
            solve(count+1);
        }
        else{  
            for(int i=1; i<N; i++){
                if(all[i]==0 && i>max_start){
                    all[i]=1;   //1이면 start 팀
                    int old_max = max_start;
                    max_start=i;
                    //재귀
                    solve(count+1);
                    //원상태로 되돌림
                    all[i]=0;
                    max_start = old_max;
                }
            }
        }
    }
}

---

문제 풀이

  Global variables(전역 변수)를 선언하여 보다 쉽게 풀 수 있는 문제입니다. N은 사람 수를 의미하고, 배열 'abilities'는 사람들의 능력치를 의미합니다. 이때 N의 최대 범위인 20으로 배열을 선언한 후, main 함수에서 값을 입력받습니다. 전역 변수 min, 배열 all, max_start는 재귀함수 'solve'에서 이용됩니다. 'solve' 재귀함수는 다음과 같이 정의합니다.

함수: solve(int count)

파라미터
- count : 재귀 반복 횟수

Base Case (기본 케이스)
- 조건문: count == N/2 (start 팀에 들어갈 인원 N/2명만 고르면 됨)
- 실행문
     start 배열에 스타트 팀 구성인원, link 배열에 링크 팀 구성인원 입력.
     스타트 팀 능력치 합, 링크 팀 능력치 합 계산 후 start_sum, link_sum에 저장.
     팀 간의 차 계산 후, 이 값이 min보다 작다면 갱신

Recursive Case (재귀 케이스)
- 조건문: count != N/2 (count가 N/2보다 작을 경우)
- 실행문
     count==0 이라면, all[0]=1 (항상 '0' 선수가 스타트 팀에 들어가도록 함)
     1부터 N-1까지, 각 선수를 스타트 팀에 추가 (all 배열 값을 1로 만듦)
     중복을 최소화하기 위해 스타트 팀의 가장 큰 숫자 선수 max_start 갱신
- 재귀: solve(count+1)

 

  전역변수 all, max_start, min부터 봅시다. 배열 'all'은 각 선수가 스타트 팀인지, 링크 팀인지 기록하기 위한 배열입니다. 모든 값은 0 또는 1이며, 값이 1이라면 스타트 팀 선수, 0이라면 링크 팀 선수입니다. 초기값은 모두 0이며, 재귀를 통해 정확히 N/2 개의 값을 1로 바꿔 스타트 팀 선수로 지정해줍니다. 이렇게 지정하는 과정에서, 'max_start' 변수는 현재까지 스타트 팀에 추가된 선수 중 가장 큰 숫자를 기록합니다. 스타트 팀에 선수를 새로 추가할 때, 항상 max_start보다 큰 선수 중 한 명을 고르도록 하여 중복을 최소화시켜줍니다. N/2번의 재귀를 거쳐 모든 선수를 스타트, 링크 팀으로 나누면 Base Case로 들어갑니다. 각 팀의 총 능력치를 계산하고, 팀 간의 차를 계산하여 변수 'diff'에 저장합니다. 이 값을 전역변수 'min'과 비교하여, 이보다 작다면 갱신합니다. 'min'은 팀을 나누는 모든 경우의 수 중, 팀 간 능력치 차의 최솟값을 저장합니다. 모든 재귀를 마치면, 최종적인 min값이 구하고자하는 정답이 됩니다.

  마지막으로 코드를 최적화시킨 방법을 설명하겠습니다. 우선, '0' 선수가 스타트 팀에 들어가는 경우만 고려합니다 (Line 60 ~ 65). 4명이 있을 때, 스타트 팀에 (0, 1) 링크 팀에 (2, 3)이 들어가는 경우와 스타트 팀에 (2, 3) 링크 팀에 (0, 1)이 들어가는 경우 팀 간 능력치 차이는 똑같습니다. 따라서 '0' 선수를 항상 스타트 팀에 넣어 중복을 없앱니다. 또한, 'max_start' 변수로 스타트 팀의 가장 큰 숫자 선수를 기록합니다. 예를 들어 6명이 있을 때, 스타트 팀에 (0, 2, 3)을 고를 때와 스타트 팀에 (0, 3, 2)을 고르는 경우는 똑같습니다. 늘 오름차순으로 숫자들을 고르도록 하면 모든 중복이 없어집니다.