알고리즘/문제 풀이

[Java/자바 swea 8458] 원점으로 집합

광규니 2021. 9. 29. 14:04
반응형

풀이

1) 좌표와 원점까리 거리 중 홀수는 홀수끼리, 짝수는 짝수끼리 존재해야 같이 도달할 수 있습니다.

좌표들 중 거리가 짝수랑 홀수가 섞여 있으면 정답 x

 

2) max값이 원점에 도달하는 거리를 계산해야합니다.

max%2 == sum%2 과 sum>= max보다 크거나 같은지 

조건을 따져주면서 sum을 1,2,3,4, 씩 더해주면서 값을 구해야합니다.

 

수학문제는 어렵네요 ㅜㅜ

import java.io.*;
import java.util.*;


class Solution {
	
	public static void main(String[] args)throws Exception{
		// TODO Auto-generated method stub
		BufferedReader br= new BufferedReader(new InputStreamReader(System.in));
		int t=Integer.parseInt(br.readLine());
		StringTokenizer st;
		for(int tc=1;tc<=t;tc++) {
			
			int N=Integer.parseInt(br.readLine());
			int[] arr=new int[N];
			int max=0;
			
			for(int i=0;i<N;i++) {
				st = new StringTokenizer(br.readLine()," ");
				int x=Integer.parseInt(st.nextToken());
				int y=Integer.parseInt(st.nextToken());
				
				arr[i]=Math.abs(x)+Math.abs(y);
				max=Math.max(max, arr[i]);
				
			}
			for(int i=1;i<N; i++) {
				if((arr[0]%2) != (arr[i]%2)) { //홀수, 짝수 같이 있으면 답 x
					System.out.println("#"+tc+" -1");
					continue next;
				}
			}
			int sum=0;
			for(int i=0 ; ; i++) {
				sum+=i;
                // max 값 비교
				if(sum>=max && (sum%2)==(max%2)) { 
					System.out.println("#"+tc+" "+i);
					break;
				}
			}	
		}
		br.close();
	}

}
반응형