2017 하반기 삼성 SW 역량 테스트 - 스타트와 링크


작성일 : 2018-12-10 02:18:24
조회수 : 469



본문

이번 문제는 2017년 하반기로 추정(?) 되는 SW 역량테스트 기출 복원문제 입니다. 2개의 팀에 멤버들을 각각 나누어 편성할 때, 팀에 같이 있음으로써 생기는 능력치들을 모두 합하였을 때 양 팀의 능력치가 차이가 최소가 되는 경우를 찾으면 됩니다.


문제를 얼핏 보았을 때는 특정한 해법을 찾아야 되나 싶은 생각이 들 수 있습니다. 하지만 왠지 이런 문제는 모든 경우를 다 따져보아야 할 것 같은 느낌이 듭니다. 그렇지만 제한된 시간내에 문제가 풀릴 수 있을 까 싶은 생각이 듭니다. 그러므로 항상 문제를 풀 때 가장 중요하게 파악해야 하는, 문제의 input 범위를 체크합니다. 인원수는 총 20명이고, 20명을 양쪽 팀에 골고루 분배해야 합니다. 즉, $C(20,10) = 184756$ 가지의 경우의 수를 계산해 봐야 함을 알 수 있습니다. 전처리를 좀 더 잘한다면, A팀에서 같이 만나던, B팀에서 같이 만나던 상관 없으므로 전체 확인해야 할 경우의 수를 $1/2$ 줄일 수 있습니다. 


각 멤버들간의 능력치 총합을 구하려면 2중 for문을 이용해 계산할 수 있습니다. 20명이 최대이므로, 양 팀의 능력치 총합은 최대 100번의 for문 연산으로 계산할 수 있습니다. 따라서 이 문제는 제한시간 내에 충분히 완전탐색할 수 있음이 확인되었습니다. 문제를 풀 때는 재귀적으로 dfs문을 이용하면 편리합니다. 다음과 같이 설계하여 함수를 만들 수 있습니다.


1. 왼쪽 팀에 들어갈 수 있다면 왼쪽 팀에 추가 후 다음 진행

2. 오른쪽 팀에 들어갈 수 있다면 오른쪽 팀에 추가 후 다음 진행

3. 모든 인원이 각 팀에 분배되었다면, 능력치 총합을 계산 후 min 값 갱신


여기까지만 생각하고 코딩하여 제출한 결과 24ms가 나와 충분히 pass 할 수 있음을 알 수 있습니다. algotirhm 헤더 파일을 include 하여 사용할 수 있다면, next_permutation 등을 이용하여 코딩할 수 있습니다.

#include <iostream>
using namespace std;

int n, hn, score[20][20], lt[10], rt[10], answer = 2e9;
int min(int a, int b) {
    return a < b ? a : b;
}
int abs(int a) {
    return a < 0 ? -a : a;
}
void dfs(int idx, int lidx, int ridx) {
    if (idx == n) {
        int left = 0, right = 0;
        for (int i = 0; i < hn; i++) {
            for (int j = 0; j < hn; j++) {
                left += score[lt[i]][lt[j]];
                right += score[rt[i]][rt[j]];
            }
        }
        answer = min(answer, abs(left - right));
        return;
    }
    if (lidx < hn) {
        lt[lidx] = idx;
        dfs(idx + 1, lidx + 1, ridx);
    }
    if (ridx < hn) {
        rt[ridx] = idx;
        dfs(idx + 1, lidx, ridx + 1);
    }
}
int main() {

    cin >> n;
    hn = n / 2;
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            cin >> score[i][j];
        }
    }
    dfs(0, 0, 0);
    cout << answer;
}

2017 하반기 삼성 SW 역량 테스트 - 스타트와 링크 - 알고리즘닷컴
취업 대비 알고리즘에서는 다양한 기업들의 기출 문제 및 경향, 풀이 등에 대한 포스팅을 다룹니다.