[SWEA] 8458 - 원점으로 집합

[문제링크]

SW Expert Academy

 

0. 가장 먼 점이 원점으로 이동할 때까지, 먼저 원점에 도달한 점들은 +1 -1 운동을 반복하게 된다

  - 모든 점들의 2로 나눈 나머지가 같지 않다면, 점들의 움직임이 일치하지 않아 한 점으로 모이는게 불가능하다

 

1. 입력받으며, 모든 수가 홀수 or 짝수로 통일되있는지 확인한다

  - 통일되있지 않으면, -1을 출력

 

2. 동시에, 입력값중 최댓값을 탐색한다

  - 모든 값이 홀/짝수로 통일되 있다면, 최댓값이 원점에 도달하는 순간 종료된다

 

3. 매 초 이동량의 누적값을 구하여 그 값이 max보다 크면서 max와의 차이가 짝수일 때 종료한다

 

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

public class Solution{
	public static void main(String[] args)throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringBuilder sb = new StringBuilder();
		
		int tc = pint(br.readLine());
		for (int testcase = 1; testcase <= tc; testcase++) {
			int N = pint(br.readLine());
			int[] len = new int[N];
			int sum=0;
			int cnt=0;
			StringTokenizer st = new StringTokenizer(br.readLine(), " ");
			len[0]= Math.abs(pint(st.nextToken())) + Math.abs(pint(st.nextToken()));
			int max=len[0];
			for (int i = 1; i < N; i++) {
				st = new StringTokenizer(br.readLine(), " ");
				len[i]= Math.abs(pint(st.nextToken())) + Math.abs(pint(st.nextToken()));
				max=Math.max(max, len[i]);
				if(len[i]%2 != len[i-1]%2) {
					cnt=-1;
				}
			}
			
			if(cnt==0) {
				while(true) {
					boolean isE=true;
					if(sum<max || (max-sum)%2!=0) {
						isE=false;
					}
					if(isE)break;
					sum+=++cnt;
				}
			}
			sb.append("#").append(testcase).append(" ").append(cnt).append("\n");
			
		}System.out.println(sb);
	}
	
	static int pint(String s) {
		return Integer.parseInt(s);
	}
}

결과 화면