[JAVA] SWEA 8458 원점으로 집합

문제

https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AWzaq5KKk_ADFAVU
N개의 격자점이 있다.

이 점들을 몇 번 움직여 모든 점을 원점((0, 0))으로 이동시키고 싶다.

한 번의 움직임은 모든 점을 움직이게 하고,

i번째 움직임에서 각 점은 상하좌우로 i만큼의 거리를 반드시 이동해야 한다.

최소 몇 번의 움직임으로 모든 점을 원점에 모을 수 있는지 구하는 프로그램을 작성하라.

입력

첫 번째 줄에 테스트 케이스의 수 T가 주어진다.

각 테스트 케이스의 첫 번째 줄에는 하나의 정수 N(1 ≤ N ≤ 10)이 주어진다.

다음 N개의 줄의 i번째 줄에는 두 정수 xi­, yi(-109 ≤ xi­, yi ≤ 109)가 공백 하나로 구분되어 주어진다.

이는 i번째 점이 (xi, yi)에 위치함을 나타낸다.

출력

각 테스트 케이스마다 ‘#x’(x는 테스트케이스 번호를 의미하며 1부터 시작한다)를 출력하고,

각 테스트 케이스마다 최소 몇 번 움직여야 모든 점이 원점에 모이는 지 출력한다.

만약 모든 점을 원점으로 이동시킬 수 없으면, -1을 출력한다.

---

풀이: 수학

이 문제에서 좌표 정보는 거리만 필요하다. 따라서 입력 값의 좌표 절대값의 합을 거리로 간주하고 저장한다.
좌표에서 떨어진 거리가 모두 홀수이거나 모두 짝수일 때만 동시에 원점 도달이 가능하다.
i번째에 움직인 거리는 $n(n+1)/2$ 이다.
움직인 거리가 초기 거리보다 크더라도 짝수만큼 크다면 원점 도달이 가능하다. (원점에서 뺑뺑이 돌면 된다.)

1. dist[]에 거리값 저장
2. dist[]가 짝수, 홀수 일관성이 없다면 원점 동시에 도달 불가.
3. 일관성이 있다면 dist[] 최대값보다 이동거리가 크면서 그 차이가 짝수가 되게 하는 i를 구한다.

---

코드

package swea;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class p원점으로집합 {
	public static void main(String[] args) throws NumberFormatException, IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st;
		int testcase = Integer.parseInt(br.readLine());
		for (int t = 1; t <= testcase; t++) {
			int N = Integer.parseInt(br.readLine());
			int[] dist = new int[N];
			int max = 0;
			for (int i = 0; i < N; i++) {
				st = new StringTokenizer(br.readLine());
				dist[i] = Math.abs(Integer.parseInt(st.nextToken())) + Math.abs(Integer.parseInt(st.nextToken()));
			}
			for (int i = 0; i < N; i++) {
				if (i >= 1 && dist[i] % 2 != dist[i - 1] % 2) {
					max = -1;
					break;
				} else {
					max = Math.max(dist[i], max);
				}
			}
			int idx = 0;

			if (max != -1) {
				long sum = 0;
				while (true) {
					sum += idx;
					if (sum >= max && (sum - max) % 2 == 0) {
						break;
					}
					idx++;
				}
			} else {
				idx = -1;
			}
			System.out.println("#" + t + " " + idx);
		}
	}
}