[SWEA] 8458. 원점으로 집합.java

SWEA에서 원점으로 집합을 자바를 통해 풀어 보았다. 

 

SW Expert Academy

 

8458. 원점으로 집합.java

GitHub - tomy9729/Algorithm: 🐗 내가 직접 작성한 내 코드 🐗

 

8458번 원점으로 집합

문제

N개의 격자점이 있다.

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

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

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

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

설명

문제 설명이 조금 부족한데 추가하자면 i번째 움직임에서 각 점은 상하좌우 모두 합쳐서 i만큼 움직일 수 있다. 예를 들어 5번째 움직임이라면 "상,상,하,하,우"와 같이 움직일 수 있다. 그리고 '한 번의 움직임은 모든 점을 움직이게 하고'의 의미는 모든 점이 같은 움직임을 가진다는 게 아니다. 각 점들이 모두 움직이되 다르게 움직일 수 있다.

 

먼저 도착한 점은 '상,하,상,하...'와 같이 같이 위치를 반복하며 움직이면 되기에 가장 멀리 있는 점의 거리를 구해야한다. 그렇기 때문에 모든 점의 거리가 모두 짝수이거나 홀수이어야 한다. 만약 모든 점의 거리가 짝수 또는 홀수가 아니라면 -1을 출력한다.

 

i번 째에는 i번만큼 움직일 수 있다. 즉 i번 째까지 움직일 수 있는 총 거리는 i*(i+1)/2이다. 가장 멀리 있는 점의 거리가 i*(i+1)/2보다 작다면 i번 째에 원점에 갈 수 있다. 단 이미 원점에 도착한 점들은 '상,하,상,하...'와 같이 같은 위치를 반복적으로 이동하고 있으므로 "i*(i+1)/2 - (가장 멀리 있는 점의 거리)"가 홀수라면 다른 점들은 원점에 존재하지 않는다. 예를 들어 "i*(i+1)/2 - (가장 멀리 있는 점의 거리)"가 3이라면 다른 점들은 '상,하,상'을 통해 (0,1)에 위치한다. i*(i+1)/2가 가장 멀리 있는 점의 거리보다 크면서 "i*(i+1)/2 - (가장 멀리 있는 점의 거리)"가 짝수인 i가 정답이다.

코드

//8458. 원점으로 집합.java
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class 원점으로_집합_8458 {
	static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
	static StringTokenizer st;
	static StringBuilder sb = new StringBuilder();
	public static void main(String[] args) throws NumberFormatException, IOException {
		int T = Integer.parseInt(br.readLine());
		for(int t=1;t<=T;t++) {
			int N = Integer.parseInt(br.readLine());
			point[] points = new point[N];
			for(int n=0;n<N;n++) {
				st = new StringTokenizer(br.readLine());
				int i = Integer.parseInt(st.nextToken());
				int j = Integer.parseInt(st.nextToken());
				points[n] = new point(i,j);
			}
			solution(points,t);
		}
		System.out.println(sb.toString());
	}
	static void solution(point[] points, int t) {
		int odd=0;
		int even=0;
		int max=0;
		for(int i=0;i<points.length;i++) {
			if(max<points[i].dis)max=points[i].dis;
			if(points[i].dis%2==0)even++;
			else odd++;
		}
		if(odd!=0 && even!=0) {
			sb.append("#"+t+" "+-1+"\n");
			return;
		}
		
		int moveCount=0;
		int i=0;
		while(true) {
			moveCount += i;
			if(moveCount>=max && (moveCount-max)%2==0) {
				sb.append("#"+t+" "+i+"\n");
				break;
			}
			i++;
		}
		
	}
	static class point{
		int i;
		int j;
		int dis;
		point(int i, int j){
			this.i=i;
			this.j=j;
			this.dis=Math.abs(i)+Math.abs(j);
		}
	}
}