[BOJ] #14889 스타트와 링크

시간 제한	메모리 제한	정답 비율
2 초	512 MB	50.576%

 

14889번: 스타트와 링크

 

방법 1 : vector 이용

Brute Force 로 스타트팀의 구성원을 구해고, 스타트팀의 구성원을 기반으로 링크팀의 구성원을 알아낸다. 그렇게 팀의 구성원을 알아낸 후에 각 팀의 능력치를 계산하여 비교하고 MIN 값을 매번 갱신시킨다.

• 함수 설명
  인자 idx는 인덱스 순서를 나타내고, cnt 는 스타트팀의 구성원이 아닌 사람의 숫자이다. 스타트팀과 링크팀의 구성원은 무조건 n/2 명이므로 스타트팀의 구성원이 아닌 사람의 숫자는 n/2를 넘어갈 수 없다. 따라서 cnt 가 n/2를 넘어가면 return 하도록 하였다.

 

메모리	시간
1176 KB	20 ms

#include <cstdio>
#include <string.h>
#include <algorithm>
#include <vector>
using namespace std;
int n, arr[25][25], chk[25], MIN = 10000;
vector<int> team1, team2;
void go(int idx, int cnt) {
    if (idx > n || cnt > n/2) return;
    if (team1.size() == n / 2) {
        // 양쪽의 팀 능력치를 비교하여 MIN 값을 구할거임.
        int sumteam1 = 0, sumteam2 = 0;
        for (int i = 0; i < team1.size(); i++) {
            chk[team1[i]] = 1;
            for (int j = i+1; j < team1.size(); j++) {
                sumteam1 += arr[team1[i]][team1[j]] + arr[team1[j]][team1[i]];
            }
        }
        for (int i = 1; i <= n; i++) {
            if (!chk[i]) team2.push_back(i);
        }
        for (int i = 0; i < team2.size(); i++) {
            for (int j = i + 1; j < team2.size(); j++) {
                sumteam2 += arr[team2[i]][team2[j]] + arr[team2[j]][team2[i]];
            }
        }
        MIN = min(MIN, abs(sumteam1 - sumteam2));
        team2.clear(); memset(chk, 0, sizeof(chk));
        return;
    }
    team1.push_back(idx);
    go(idx + 1, cnt);
    team1.pop_back();
    go(idx + 1, cnt + 1);
}
int main() {
    scanf("%d", &n);
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= n; j++) {
            scanf("%d", &arr[i][j]);
        }
    }
    go(1, 0);
    printf("%d", MIN);
    return 0;
}

매번 기저단계에서 배열 초기화를 시켜야하기 때문에 부담이 큰 단점이 있다. 그래서 방법 2를 사용해 보았다.

 

방법 2 : vector 이용 시간 단축.

이 방법은 매번 n 크기의 배열을 모두 탐색해야하지만 배열을 초기화해야하는 부담이 적어지기 때문에 시간이 크게 절약되어 '방법 1'보다 효율적인 코드가 된다.

그리고 '방법 1'에서 사용했던 cnt를 방법 2에서 사용하면 n 명의 팀원 모두를 만날 수 없어 예상하는 결과값과 다른 값이 나오게 되어 빼주어야 한다. 

메모리	시간
1176 KB	4 ms

#include <cstdio>
#include <string.h>
#include <algorithm>
#include <vector>
using namespace std;
int n, arr[25][25], MIN = 10000;
vector<int> team1, team2;
void go(int idx) {
    if (!MIN) return; // 차이가 0이라면 더 이상 보지 않아도 됨. 
    if (idx > n) {
        // 양쪽의 팀 능력치를 비교하여 MIN 값을 구한다.
        int sumteam1 = 0, sumteam2 = 0;
        for (int i = 0; i < team1.size() - 1; i++) {
            for (int j = i + 1; j < team1.size(); j++) {
                sumteam1 += arr[team1[i]][team1[j]] + arr[team1[j]][team1[i]];
                sumteam2 += arr[team2[i]][team2[j]] + arr[team2[j]][team2[i]];
            }
        }
        MIN = min(MIN, abs(sumteam1 - sumteam2));
        return;
    }
    if (team1.size() < n / 2) {
        team1.push_back(idx);
        go(idx + 1);
        team1.pop_back();
    }
    if (team2.size() < n / 2) {
        team2.push_back(idx);
        go(idx + 1);
        team2.pop_back();
    }
}
int main() {
    scanf("%d", &n);
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= n; j++) {
            scanf("%d", &arr[i][j]);
        }
    }
    go(1);
    printf("%d", MIN);
    return 0;
}

 

방법 3 : int 배열 이용

메모리도, 시간도 모두 절약되는 최적의 방법이다.

메모리	시간
1116 KB	0 ms

#include<cstdio>
#include<math.h>
int n, a[20][20], t1[10], t2[10], an, bn, ans = 1e5;
void go(int x) {
    if (!ans) return;
    if (x == n) {
        int s1 = 0, s2 = 0;
        for (int i = 0; i < n / 2 - 1; i++)
            for (int j = i + 1; j < n / 2; j++) {
                s1 += a[t1[i]][t1[j]] + a[t1[j]][t1[i]];
                s2 += a[t2[i]][t2[j]] + a[t2[j]][t2[i]];
            }
        s1 = abs(s1 - s2);
        ans = ans < s1 ? ans : s1;
        return;
    }
    if (an < n / 2) {
        t1[an++] = x;
        go(x + 1);
        an--;
    }
    if (bn < n / 2) {
        t2[bn++] = x;
        go(x + 1);
        bn--;
    }
}
int main() {
    scanf("%d", &n);
    for (int i = 0; i < n; i++)
        for (int j = 0; j < n; j++)
            scanf("%d", &a[i][j]);
    go(0);
    printf("%d", ans);
}

 

 

마무리

스타트와 링크를 풀면서 vector가 일반 int 배열보다 메모리와 시간을 많이 사용하게 된다는 점을 크게 깨닫게 되었다. 물론 메모리부분은 헤더?의 영향이 있을 것 같지만! 확실히 인덱스로만 움직이는 것과 함수(pop_back, push_back)을 쓰는 것은 큰 차이구나 싶었다.