[Java/수학] SWEA. 원점으로 집합

SW Expert Academy

🤔 Intuition

수학? 아이디어? 문제다.

이 문제의 아이디어는,

1. 주어진 점들의 맨해튼 거리가 짝수로만 or 홀수로만 이어져 있는 경우에만 이동이 가능하다.
2. 맨해튼 거리가 가장 큰 숫자가 들어올 수 있으면 다른 점은 알아서 들어온다.

 따라서 원점으로부터의 거리가 짝수로만/홀수로만 주어지는 점들에 대하여, 가장 먼 점을 몇 번 만에 원점으로 끌어올 수 있는지만 고려하면 된다.

 

🔎 Algorithm & Complexity

* @algorithm math
* @time O(N) -> 265 ms
* @memory O(1) -> 51,712 kb

👨🏻‍💻 Logic

1. 짝수로만 or 홀수로만 거리가 주어졌는지 검사하고, 맞을 때만 진행
2. sum(i)가 최대 거리를 넘어설 때의 i가 원점을 최초로 터치하는 i이다. 이 때, sum(i)에서 최대 거리를 빼주면, 원점으로 가야 하는 남은 거리가 나오는데, 이게 짝수가 될 때 원점으로 도달이 가능하다고 판단할 수 있다. (수학적 사고)

public class SWEA_원점으로집합 {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringBuilder sb = new StringBuilder();
        StringTokenizer st;

        int T = Integer.parseInt(br.readLine());
        for (int tc = 1; tc <= T; tc++) {
            solution(br, sb, tc);
        }
        System.out.println(sb.toString());
    }

    private static void solution(BufferedReader br, StringBuilder sb, int tc) throws IOException {
        StringTokenizer st;
        long n = Integer.parseInt(br.readLine());
        long max = -1;
        int oddBit = 0;
        boolean flag = false;
        for (int i = 0; i < n; i++) {
            st = new StringTokenizer(br.readLine());
            long a = Integer.parseInt(st.nextToken());
            long b = Integer.parseInt(st.nextToken());
            long abs = Math.abs(a) + Math.abs(b);
            if (i == 0) {
                oddBit = abs % 2 == 1 ? 1 : 0;
            } else {
                if ((abs % 2 != oddBit) && !flag) {
                    flag = true;
                }
            }
            max = Math.max(max, abs);
        }
        if (flag) {
            sb.append(String.format("#%d -1\n", tc));
            return;
        }
        // max가 구해진 상황
        long i = 0;
        long j = 0;
        while (j < max) {
            j += ++i;
        }
        j -= max;
        while (j % 2 == 1) {
            j += ++i;
        }
        sb.append(String.format("#%d %d\n", tc, i));
    }
}