정범의 프로그래밍 블로그 입니다.

4 분 소요

1. 핵심 개념 및 근거

핵심 개념

  • 백터의 성질: 지렁이 $i$에서 지렁이 $j$로 이동할 때의 벡터는 $(x_j - x_i, y_j - y_i)$입니다. 모든 지렁이가 짝을 지어 이동할 때, 전체 벡터의 합은 다음과 같이 표현됩니다
    • $\sum (\vec{V}{dest} - \vec{V}{start})$
    • 즉, (도착점 좌표들의 합) - (시작점 좌표들의 합)으로 단순화할 수 있습니다.
  • 조합: $N$마리의 지렁이 중 절반인 $N/2$마리를 ‘시작점’으로 선택하면, 나머지 절반은 자동으로 ‘도착점’이 됩니다.

근거 및 제약 사항

  • 제약 사항: $N$은 최대 20입니다. 20마리 중 10마리를 선택하는 경우의 수는 ${20}C{10} = 184,756$으로 매우 적습니다. 따라서 완전 탐색(DFS)이 가능합니다.
  • 시간 복잡도: $O(T \times \binom{N}{N/2})$


2. 추론 과정

  1. “모든 지렁이가 짝을 짓는다”: 짝을 짓는다는 것은 출발지와 목적지가 결정된다는 뜻입니다.
  2. “벡터의 합의 최솟값”: 각 벡터를 일일이 구해서 더하는 것보다, 벡터의 원리($\text{End} - \text{Start}$)를 이용해 식을 정리하면 $N$개 중 $N/2$개의 부호를 결정하는 문제로 바뀝니다.
  3. “N=20”: 이 숫자는 “지수 시간 복잡도나 조합을 써도 된다”는 강력한 힌트입니다


3. 설계 및 접근

  1. 입력 저장: 지렁이들의 좌표 $(x, y)$를 클래스에 저장합니다.
  2. DFS(조합) 구현: $N$마리 중 $N/2$마리를 뽑는 combination 함수를 만듭니다.
  3. 결과 계산
    • 선택된 지렁이들의 좌표는 모두 더하고(sumX += x, sumY += y)
    • 선택되지 않은 지렁이들의 좌표는 모두 뺍니다(sumX -= x, sumY -= y).
  4. 최솟값 갱신: 최종 벡터 $(X, Y)$의 길이의 제곱($X^2 + Y^2$)을 구해 전역 최솟값을 갱신합니다.


4. 예시 시뮬레이션

  • 상황: 지렁이가 4마리(A, B, C, D)라고 가정합시다.
  • 우리는 2마리를 ‘도착점’으로 골라야 합니다. 만약 A, B를 골랐다면:
  • 벡터의 총합 $V = (A+B) - (C+D)$
  • $X_{total} = (x_A + x_B) - (x_C + x_D)$
  • $Y_{total} = (y_A + y_B) - (y_C + y_D)$
  • 결과값 $= X_{total}^2 + Y_{total}^2$


5. 주의 사항

  • 데이터 타입
    • 좌표의 합을 제곱하는 과정에서 숫자가 매우 커질 수 있습니다.
    • 반드시 long 타입을 사용해야 오버플로우를 방지할 수 있습니다.
    • 최솟값 변수를 Long.MAX_VALUE로 초기화하세요.


6. 코드 풀이

6.1 지렁이 클래스 선언

static class Worm {
        int x, y;
 
        public Worm(int x, int y) {
            super();
            this.x = x;
            this.y = y;
        }
    }
  • 지렁이들의 좌표를 저장하는 클래스 입니다.

6.2 조합 구현

static void dfs(int level, int count) {
 
        // N/2마리를 선택하면 종료
        if (count == N / 2) {
            cal();
            return;
        }
 
        // N까지 탐색했는데 N/2가 되지 않으면 종료
        if (level == N)
            return;
 
        // 선택
        selected[level] = true;
        dfs(level + 1, count + 1);
 
        // 미선택
        selected[level] = false;
        dfs(level + 1, count);
 
    } // dfs 종료
  • N/2마리를 선택했다면 결과를 계산하고 종료합니다.
  • N까지 탐색했는데 N/2가 되지 않으면 종료합니다.
  • 지렁이를 선택하면 dfs(level + 1, count + 1);
  • 지렁이를 선택하지 않았다면 dfs(level + 1, count);

6.3 결과 계산 구현

 static void cal() {

        long totalX = 0;
        long totalY = 0;
 
        for (int i = 0; i < N; i++) {
 
            // 선택하면 더한다.
            if (selected[i]) {
                totalX += worms.get(i).x;
                totalY += worms.get(i).y;
            }
            // 미선택이면 뺀다.
            else {
                totalX -= worms.get(i).x;
                totalY -= worms.get(i).y;
            }
        }
 
        // 현재 벡터의 크기 계산
        long curvector = totalX * totalX + totalY * totalY;
 
        // 갱신
        result = Math.min(result, curvector);
 
    } // cal 종
  • totalX, totalY 초기화: 합산된 최종 벡터의 $x$성분과 $y$성분을 저장할 변수입니다.
  • 부호 결정: selected[i]가 true인 $N/2$마리는 플러스(+) 기호를, false인 나머지 $N/2$마리는 마이너스(-) 기호를 적용합니다.
  • 제곱 계산: 문제에서 요구하는 값은 벡터 길이의 제곱입니다. 피타고라스 정리에 의해 길이는 $\sqrt{X^2 + Y^2}$이므로, 제곱값은 $X^2 + Y^2$이 됩니다.

6. 전체 코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.List;
import java.util.StringTokenizer;
 
public class Solution {
 
    static class Worm {
        int x, y;
 
        public Worm(int x, int y) {
            super();
            this.x = x;
            this.y = y;
        }
    }
 
    static List<Worm> worms; // 지렁이 좌표 모음
    static int N; // 지렁이의 수
    static long result; // 벡터의 합의 크기의 최솟값
    static boolean[] selected; // 지렁이 선택 체크
 
    public static void main(String[] args) throws NumberFormatException, IOException {
        // TODO Auto-generated method stub
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringBuilder sb = new StringBuilder();
 
        int T = Integer.parseInt(br.readLine().trim());
 
        // tc 수행
        for (int tc = 1; tc <= T; tc++) {
 
            // 초기화
            N = Integer.parseInt(br.readLine());
            worms = new ArrayList<>();
            result = Long.MAX_VALUE;
            selected = new boolean[N];
 
            // 지렁이 좌표 입력
            for (int i = 0; i < N; i++) {
                StringTokenizer st = new StringTokenizer(br.readLine());
                int x = Integer.parseInt(st.nextToken());
                int y = Integer.parseInt(st.nextToken());
                worms.add(new Worm(x, y));
            }
 
            // 처리
            dfs(0, 0);
 
            // 출력 내용 추가
            sb.append("#" + tc + " " + result + "\n");
 
        } // tc 종료
 
        // 출력
        System.out.println(sb);
 
    } // main 종료
 
    // 지렁이를 매칭하는 함수
    static void dfs(int level, int count) {
 
        // N/2마리를 선택하면 종료
        if (count == N / 2) {
            cal();
            return;
        }
 
        // N까지 탐색했는데 N/2가 되지 않으면 종료
        if (level == N)
            return;
 
        // 선택
        selected[level] = true;
        dfs(level + 1, count + 1);
 
        // 미선택
        selected[level] = false;
        dfs(level + 1, count);
 
    } // dfs 종료
 
    // 조합 계산
    static void cal() {
 
        long totalX = 0;
        long totalY = 0;
 
        for (int i = 0; i < N; i++) {
 
            // 선택하면 더한다.
            if (selected[i]) {
                totalX += worms.get(i).x;
                totalY += worms.get(i).y;
            }
            // 미선택이면 뺀다.
            else {
                totalX -= worms.get(i).x;
                totalY -= worms.get(i).y;
            }
        }
 
        // 현재 벡터의 크기 계산
        long curvector = totalX * totalX + totalY * totalY;
 
        // 갱신
        result = Math.min(result, curvector);
 
    } // cal 종료
 
}

카테고리:

업데이트:

참고