[SWEA] D4 8458번 원점으로 집합 (JAVA)

문제 출처 - SW Expert Academy

문제는 여기

SW Expert Academy

[문제] 

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을 출력한다.

 

 

---

[풀이]

1. 먼저 입력되는 값들의 좌표를 해당 군으로 맞춰준다.

2. 군들이 홀수인지 짝수인지 체크해준다.

3. 군들의 최고값을 구한다.

4. 최고값을 기준으로 1부터 i값을 늘려가며 누적 합을 구한다.

5. 최고값이 누적 합보다 작고 누적합 - 최고값이 짝수일 때 결과를 출력한다.

[접근]

1. (x, y)의 값을 (x, 0) 혹은 (0, y)처럼 한 직선 위로 옮겨서 생각한다.

2. 누적 합의 값이 짝수일 때는 짝수만큼만 이동이 가능하고 홀수일 때는 홀수로만 이동이 가능하다.

3. 주어지는 값들의 홀수, 짝수의 유무가 일치되지 않는다면 무조건 불가능하다.

4. 누적합 - 최고값이 짝수 값일 때 결과를 출력하는 이유는 짝수 - 짝수 or 홀수 - 홀수 일 때 짝수이기 때문이다.

 

[코드]

package swet;

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

public class Solution_D4_8458 {
	static int T;
	static int n;
	static int[] x; // 각 x좌표를 받기위한 배열
	static int[] y; // 각 y좌표를 받기위한 배열
	static int result; // 결과값 변수
	static boolean[] odd; // 홀수인지를 저장하기 위한 배열
	
	public static void main(String[] args) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		
		T = Integer.parseInt(br.readLine());
		
		start :
		for (int t = 1; t <= T; t++) {
			n = Integer.parseInt(br.readLine());
			
			x = new int[n];
			y = new int[n];
			odd = new boolean[n];
			Arrays.fill(odd, false); // 모든 값을 false로 초기화
			
			result = 0;
			long max = Integer.MIN_VALUE;
			
			for (int i = 0; i < n; i++) {
				StringTokenizer st = new StringTokenizer(br.readLine());
				
				x[i] = Integer.parseInt(st.nextToken());
				y[i] = Integer.parseInt(st.nextToken());
				
				int goon = Math.abs(x[i]) + Math.abs(y[i]); // 절대값으로 구해 최고값을 매겨준다
				// 3,1일때와 4,0일때의 결과값은 동일하기 때문에
				// x,y의 좌표로 두지 않고 한 직선 위에 오도록 해준다.
				max = Math.max(max, goon); // 최고값을 저장
				if (goon % 2 == 1) // 홀수인지 짝수인지 체크
					odd[i] = true;
			}
			
			// 만약 전부 다 짝수거나 홀수가 아니면 불가능하다.
			boolean check = odd[0];
			for (int i = 1; i < n; i++) {
				if (check != odd[i]) { // 만약에 처음의 값과 다른 값이 나온다면
					System.out.println("#" + t + " -1"); // -1을 출력해주고
					continue start; // 시작으로 이동한다.
				}
			}
			
			int i = 1;
			int sum = 0; // 누적합 변수
			while (true) {
				// sum의 값이 짝수일때는 짝수로만 이동 가능하고, 홀수일때는 홀수로만 이동 가능
				// max값보다 합이 크고 |max - sum|의 값이 짝수일 때
				if (sum >= max && Math.abs(sum - max) % 2 == 0)
					break;
				sum += i;
				i++;
				result++;
			}
			
			System.out.println("#" + t + " " + result);
		}
	}
}