8458. 원점으로 집합 - 자바(JAVA)

https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AWzaq5KKk_ADFAVU 

SW Expert Academy

 

문제 해석

N개의 정점이 존재하며 이 정점들을 원점으로 이동시키려고 합니다.

정점들은 상하좌우로 움직일 수 있으며, i번째 움직임에서는 i번 움직이는 특성을 가지고 있습니다.

이때 최소 몇 번의 이동만에 원점으로 이동할 수 있는지 구하세요

 

문제 풀이 전 설계

1. 가장 먼 점이 원점으로 이동할 때까지, 먼저 원점에 도달한 점들은 +1, -1 운동을 반복하게 됩니다.

(즉, 모든 점들은 모두 홀수이거나 짝수여야합니다)

 

2. 최댓값이 원점에 도달하는 순간에 종료됩니다.

 

3. Math.abs(누적합 - 최고값)이 짝수 값일 때 결과를 출력하는 이유는 짝수 - 짝수 or 홀수 - 홀수 일 때 짝수이기 때문입니다.
즉, 최고값보다 큰 누적합이 존재할 때 최고값과 누적합은 모두 짝수 거나/ 홀수여야 도착이 가능하기 때문입니다.

 

 

코드

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 Pos {
        int y;
        int x;

        public Pos(int x, int y) {
            this.x = x;
            this.y = y;
        }
    }

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int T = Integer.parseInt(br.readLine());

        StringBuilder sb = new StringBuilder();
        StringTokenizer st = null;
        List<Pos> coords = null;
        for (int tc = 1; tc <= T; tc++) {
            int N = Integer.parseInt(br.readLine());
            coords = new ArrayList<>();
            for (int i = 0; i < N; i++) {
                st = new StringTokenizer(br.readLine(), " ");
                int x = Integer.parseInt(st.nextToken());
                int y = Integer.parseInt(st.nextToken());
                coords.add(new Pos(x, y));
            }

            sb.append("#" + tc + " " + getResult(coords) + "\n");
        }
        System.out.print(sb.toString());
    }

    private static int getResult(List<Pos> coords) {

        int maxDistance = Integer.MIN_VALUE;

        //최소 1개의 점이
        //모든수가 홀수/ 짝수로 동일해야합니다.
        int firstDistance = Math.abs(coords.get(0).x) + Math.abs(coords.get(0).y);
        boolean firstValueisEven = (firstDistance % 2 == 0) ? true : false;

        for (Pos cur : coords) {
            int curDistance = Math.abs(cur.x) + Math.abs(cur.y);
            //짝수인데 처음수가 홀수임
            if (curDistance % 2 == 0 && !firstValueisEven) {
                return -1;
            }
            //홀수인데 처음수가 짝수임
            if (curDistance % 2 != 0 && firstValueisEven) {
                return -1;
            }
            maxDistance = Math.max(curDistance, maxDistance);
        }

        int sum = 0, i = 0;

        while (true) {
            sum += i;

            //누적합 - 최고값이 짝수 값일 때 결과를 출력하는 이유는 짝수 - 짝수 or 홀수 - 홀수 일 때 짝수이기 때문.
            //즉, 최고값보다 큰 누적합이 존재할때 최고값과 누적합은 모두 짝수거나/ 홀수여야 한다는 말
            if (sum >= maxDistance && Math.abs(sum - maxDistance) % 2 == 0) {
                return i;
            }
            i++;
        }


    }
}