알고리즘/문제 풀이
[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();
}
}
반응형