[SWEA] 8458. 원점으로 집합

[SWEA]D4 8458 원점으로 이동

 

 

문제링크

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

SW Expert Academy

 

* 일단 문제를 정독 하고 1시간 이상 반드시 고민이 필요합니다.

 

동영상 설명

1시간 이상 고민 했지만 아이디어가 떠오르지 않는다면 동영상에서 약간의 힌트를 얻어봅시다.

https://youtu.be/DjoAnAKp1B4

 

 

소스보기

동영상 설명을 보고도 전혀 구현이 안된다면 연습 부족입니다.
소스를 보고 작성해 본 후 스스로 백지 상태에서 3번 작성해 볼 의지가 있다면 소스를 살짝 보세요.

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

/**
 * @author 은서파
 * @since 2022/04/11
 * @see https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AWzaq5KKk_ADFAVU
 * @git 
 * @youtube  
 * @performance 36,644 kb, 233 ms
 * @category #
 * @note 
 */

public class SWEA_D4_8458_원점으로집합{
    private static BufferedReader input = new BufferedReader(new InputStreamReader(System.in));
    private static StringBuilder output = new StringBuilder();
    private static StringTokenizer tokens;

    private static int T, N;
    public static void main(String[] args) throws IOException {
        input = new BufferedReader(new StringReader(src));
        T = Integer.parseInt(input.readLine());
        for(int t=1; t<=T; t++){
            N = Integer.parseInt(input.readLine());

            int mod = -1;
            int maxGap = Integer.MIN_VALUE;
            boolean notSameMod = false;

            for(int n=0; n<N; n++){
                tokens = new StringTokenizer(input.readLine());
                int x = Integer.parseInt(tokens.nextToken());
                int y = Integer.parseInt(tokens.nextToken());
                // 원점에서의 거리
                int gap = Math.abs(x) + Math.abs(y);
                if(n==0){
                    mod = gap%2;
                    maxGap = gap;
                }else{
                    if(mod!=gap%2){
                        notSameMod = true;
                    }else{
                        maxGap = Math.max(maxGap, gap);
                    }
                }
            }// 입력 완료!!

            int answer = 0;
            if(notSameMod){
                answer = -1;
            }else{
                while(maxGap>0){
                    answer++;
                    maxGap-=answer;
                }
                maxGap*=-1;

                // maxGap==짝수 --> 지그재그 신공
                // maxGap ==홀수, 현재의 answer에 따라 달라짐.
                if(maxGap%2==1){
                    if(answer%2==0){
                        answer+=1;
                    }else{
                        answer+=2;
                    }
                }
            }
            output.append(String.format("#%d %d%n", t, answer));
        }
        System.out.println(output);
    }

	// REMOVE_START
	static String src = "3\r\n" +
			"2\r\n" +
			"0 2\r\n" +
			"2 0\r\n" +
			"2\r\n" +
			"-6 0\r\n" +
			"3 3\r\n" +
			"2\r\n" +
			"-5 0\r\n" +
			"2 1";
	// REMOVE_END
}