[Java] SWEA 8458.원점으로 집합 D4

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

SW Expert Academy

 

(문제에서 주어진 조건설명이 살짝 부족한 문제여서 혼동의 여지가 많습니다.)

 

원점에서 각기 다른 거리만큼 떨어져 있는 점들은 1... N칸씩 움직여서 모두가 원점에 도착하게 하는 게 목표입니다.

이때 N칸은 상하좌우 어느 방향으로든 나누어 움직일 수 있습니다.

(N이 3칸일때 상상좌 상하상 이런 식으로 움직일 수 있습니다. 단, 자기 자리에서 움직이지 않는 건 안됩니다.)

 

가만히 생각해보면 원점에 먼저 도착한 점들은 원점에서 진동하듯 좌우로 움직이기만해도 된다는 걸 알 수 있습니다.

예를 들어서, N=3일때 원점에 도착한 점 A는 다음 N=4의 움직임에서 좌우좌우로 움직이면 그대로 원점입니다.

다만 이후 N=5일때 움직이면 어떻게 움직이던지 원점에서 한 칸 이상 나가게 됩니다.

 

여기서 아이디어를 얻어 우리는 홀짝을 이용해 점들이 원점에 모두 모일 수 있는지 없는지를 알 수 있습니다.

원점으로부터의 거리가 모두 홀수거나 모두 짝수면 어떤 N일 때 확실하게 원점으로 모일 수 있으나, 거리가 홀수와 짝수가 섞여 있다면 어떤 방법으로도 동시에 원점에 멈추는 게 불가능합니다.

 

점 A가 원점에서 한 칸, B가 두 칸 떨어진 테스트케이스가 있다고 해봅시다.

처음 N=1일때 점 A는 원점으로 들어갑니다. 점 B는 원점으로 향하지만 한 칸 떨어진 위치에 멈춥니다.

다음 N=2일때 점 A는 좌우로 움직여 그대로 원점에 남습니다. 점 B는 원점을 지나 다시 한 칸 떨어집니다.

N=3일땐 반대로 점 B가 원점에 들어가고 좌우로 움직여 원점에 남습니다. 하지만 점 A가 원점에서 나가게 됩니다.

어떤 방법으로도 점 A와 B가 둘 다 원점에 들어가게 할 수 없습니다.

 

이렇게 해결할 수 없는 경우를 걸러내고, 이제 몇 칸을 움직여야 원점에 들어갈 수 있는지를 계산해봅시다.

 

위에서 말했다시피 원점에 먼저 도착한 점들은 원점에서 왕복운동을 하면서 대기하면 됩니다.

즉 우리는 원점에서 가장 멀리있는 점만 생각하면 됩니다. 

 

가장 멀리있는 점이 원점으로 도착했을때도 분기가 나뉩니다.

 

예를들어 가장 멀리있던 점이 8칸 떨어져 있었다고 생각해봅시다.

N=1, N=2, N=3을 지나며 다른 점들은 원점에 도달해 왕복운동을 하며 대기합니다.

N=4일때 가장 멀리있던 점이 원점에 도착합니다. 하지만 두번의 움직임이 남습니다.

 

이 남은 움직임이 짝수라면, 먼저 도착한 점들과 같이 왕복운동을 해 소모하면 됩니다.

홀수라면, 다음 기회를 노려야합니다. 즉, 다시 한 번 홀수번 움직여 원점에 맞춰야합니다.

 

정리하면 

1. 점들이 모두 홀수거나 모두 짝수여야 원점에 모이는게 가능하다.

2. 가장 먼 점에서부터 N을 늘려가며 거리를 줄인다.

3. 가장 먼 점이 원점에 도착했을때, 남은 횟수가 짝수라면 바로 종료, 홀수라면 홀수번 움직여야 종료된다.

(원점에 도착했을때의 움직임이 짝수였다면 다음 홀수번으로, 원점에 도착했을때의 움직임이 홀수였다면 짝수,홀수번 2번의 움직임을 더 해야 종료할 수 있습니다.)

 

 

설명도 조금 미흡했고 이해하기도 어려웠던 원점으로집함 문제였습니다. 감사합니다.

 

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

public class q8458_SWEA_원점으로집합 {
	static StringTokenizer st;
	static StringBuilder sb = new StringBuilder();

	public static void main(String[] args) throws NumberFormatException, IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

		int T = Integer.parseInt(br.readLine());

		for (int tc = 1; tc <= T; tc++) {
			int answer = 0;
			boolean flag = false;
			int N = Integer.parseInt(br.readLine());

			st = new StringTokenizer(br.readLine());
			long X = Integer.parseInt(st.nextToken());
			long Y = Integer.parseInt(st.nextToken());
			long odd = (Math.abs(X) + Math.abs(Y)) % 2;
			long gap = Math.max(0, Math.abs(X) + Math.abs(Y));

			for (int n = 1; n < N; n++) {
				st = new StringTokenizer(br.readLine());
				X = Integer.parseInt(st.nextToken());
				Y = Integer.parseInt(st.nextToken());

				if ((Math.abs(X) + Math.abs(Y)) % 2 != odd) {
					flag = true;
				}

				gap = Math.max(gap, Math.abs(X) + Math.abs(Y));
			}

			if (flag) {
				sb.append("#").append(tc).append(" -1").append("\n");
			} else {

				while (gap > 0) {
					answer++;
					gap -= answer;
				}
				answer = gap % 2 == 0 ? answer : (answer % 2 == 0 ? answer + 1 : answer + 2);

				sb.append("#").append(tc).append(" ").append(answer).append("\n");
			}
		}

		System.out.println(sb);
	}
}