[SWEA] 1494 : 사랑의 카운슬러

1494 : 사랑의 카운슬러

풀이

백트래킹

n범위가 20까지지만 next_permutation(v.begin+n/2,v.end()) 이렇게 하면

n이 20일때 10부터 19까지만 순열도니까 괜찮지 않을까 해서 퍼뮤테이션으로 비벼봤는데,

시간초과로 안된당…ㅠ 왜안되는지 설명해줄사람 -()/ !!

그래서 n이 20일때 2^n까지 허용되므로

하나씩 넣었다가 빼보는 방법(백트래킹)으로 다시풀었다.

퍼뮤테이션과 이방법이 시간차이가 별로 안난다고 생각헀는데 차이가 꽤 크구나.

코드

#include <iostream>
#include <vector>
#include <algorithm>
#include <string>
#include <cstring>
#include <queue>
using namespace std;

int arr[20][2];
int chk[20];
long long ans=-1;
int n;
void go(int idx,int cnt) {
    //종료조건
    if (cnt == n / 2) {
        long long xsum=0, ysum = 0;
        for (int i = 0; i < n; i++) {
            if (chk[i] == 1) {
                xsum += arr[i][0];
                ysum += arr[i][1];
            }
            else {
                xsum -= arr[i][0];
                ysum -= arr[i][1];
            }
        }
        if (ans == -1 || xsum*xsum + ysum*ysum < ans) {
            ans = xsum*xsum + ysum*ysum;
        }
        return;
    }

    for (int i = idx; i < n; i++) {
        if (chk[i] == 0) {
            chk[i] = 1;
            go(i + 1, cnt + 1);
            chk[i] = 0;
        }
    }
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);

    int T;
    cin >> T;
    for (int tc = 1; tc <= T; tc++) {
        ans = -1;
        memset(chk, 0, sizeof(0));
        cin >> n;
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < 2; j++) {
                cin >> arr[i][j];
            }
        }
        go(0,0);
        cout << "#" << tc << ' ' << ans << '\n';
    }
    return 0;
}

Written on April 5, 2019