[SW Expert Academy] 1494 사랑의 카운슬러 [Java]

[ 핵심풀이 ]

모든 백터의 합의 최소가 되는 경우를 구하면된다!

 

백터는 방향을 가진 화살표이다. 라고만 알고있었고 어떻게만들어지는지 몰랐다.

두 좌표 A: {x1, y2}, B: {x2, y2}가 있을 때 나올 수 있는 벡터는

1) A→B (x2-x1, y2-y1)

2) B→A (x1-x2, y1-y2) 두가지가 나올수 있다.

즉 벡터는 한좌표에서 다른좌표를 뺀 값이라 할 수 있다.

 

문제에서 주어진것은 모든 벡터의 합이므로

쌍을 만들었을 때 A→B로가는경우 B→A로 가는경우를 visit으로 판별하고

전체 x, y값에 정방향의경우 +, 역방향의경우 - 를 해주면된다.

[ 핵심소스 ]

// 모든벡터의 합 구하기, 짝의개수는 전체의 절반이므로 cnt==ew/2
if (cnt == ew/2) {
    long x=0,y=0;
    for(int i=0;i<ew;i++) {
        if (visit[i]) {
            y+= earthworm.get(i).getY();
            x+= earthworm.get(i).getX();
        }
        else {
            y-= earthworm.get(i).getY();
            x-= earthworm.get(i).getX();
        }
    }
    result = Math.min(result, x*x+y*y);
    return;
}

// 쌍 구하는 방식(dfs)
for(int i=index;i<ew;i++) {
    if (!visit[i]) {
        visit[i] = true;
        solve(i+1, cnt+1);
        visit[i] = false;
    }
}

[ Java ]

import java.util.ArrayList;
import java.util.Scanner;

class xy_1494{
    int y;
    int x;
    xy_1494(int y, int x) {
        this.y=y;
        this.x=x;
    }
    public int getY() {
        return y;
    }
    public void setY(int y) {
        this.y = y;
    }
    public int getX() {
        return x;
    }
    public void setX(int x) {
        this.x = x;
    }
}
public class _1494_사랑의카운슬러 {
    static final int MAX = 21;
    static int ew;
    static long result;
    static boolean visit[] = new boolean[MAX];
	
    static ArrayList<xy_1494> earthworm = new ArrayList<xy_1494>();
	
    static void init() {
        Scanner sc = new Scanner(System.in);
        int tc = sc.nextInt();
        for(int t=1;t<=tc;t++) {
            ew = sc.nextInt();
            earthworm.clear();
            for(int e=0;e<ew;e++) {
                int ey=sc.nextInt();
                int ex=sc.nextInt();
                earthworm.add(new xy_1494(ey,ex));
            }
            result = Long.MAX_VALUE;
            solve(0, 0);
            System.out.println("#"+t+" "+result);
        }
        sc.close();
    }
    static void solve(int index, int cnt) {
        if (cnt == ew/2) {
            long x=0,y=0;
            for(int i=0;i<ew;i++) {
                if (visit[i]) {
                    y+= earthworm.get(i).getY();
                    x+= earthworm.get(i).getX();
                }
                else {
                    y-= earthworm.get(i).getY();
                    x-= earthworm.get(i).getX();
                }
            }
            result = Math.min(result, x*x+y*y);
            return;
        }
        for(int i=index;i<ew;i++) {
            if (!visit[i]) {
                visit[i] = true;
                solve(i+1, cnt+1);
                visit[i] = false;
            }
        }
    }
    public static void main(String[] args) {
        init();
    }
}