내일은 알고리즘

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

https://nodingco.tistory.com/77

Java코드와 풀이 접근방법은 위쪽 포스팅에서 확인해주세요.

class Operation:
    def __init__(self, plus, minus, multiple, divide):
        self._plus = plus
        self._minus = minus
        self._multiple = multiple
        self._divide = divide

def dfs(value, count, operation):
    global minValue
    global maxValue

    if(count == N):
        minValue = min(minValue, value)
        maxValue = max(maxValue, value)
        return
    
    if(operation._plus > 0):
        operation._plus -= 1
        dfs(value + number[count], count+1, operation)
        operation._plus += 1
    if(operation._minus > 0):
        operation._minus -= 1
        dfs(value - number[count], count+1, operation)
        operation._minus += 1
    if(operation._multiple > 0):
        operation._multiple -= 1
        dfs(value * number[count], count+1, operation)
        operation._multiple += 1
    if(operation._divide > 0):
        operation._divide -= 1
        dfs(int(value / number[count]), count+1, operation)
        operation._divide += 1

def createOperation(tempOp):
    operation = Operation(tempOp[0],tempOp[1],tempOp[2],tempOp[3])
    return operation

T = int(input())
for test_case in range(1, T + 1):
    minValue = 100_000_001
    maxValue = -100_000_001
    N = int(input())
    operation = createOperation(list(map(int, input().split())))
    number = list(map(int, input().split()))

    dfs(number[0], 1, operation)

    print("#{} {}".format(test_case, maxValue-minValue))

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

숫자카드는 고정되어 있고 그 사이에 들어갈 연산자만 정해주면 됩니다.

연산의 순서는 우리가 기존에 알던 수학과 달리 무조건 좌측부터 진행됩니다.

조금 더 효율적인 계산을 위해 연산자를 모두 정하고 나서 계산하지 않고, 재귀함수 내부에서 값을 가진 채 진행하면서 구현했습니다.

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

public class q4008_SWEA_숫자만들기 {
	static StringTokenizer st;
	static StringBuilder sb = new StringBuilder();
	static int N, max, min;
	static int[] num;
	
	public static void main(String[] args) throws NumberFormatException, IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		
		int T = Integer.parseInt(br.readLine());
		int answer;
		
		for(int tc = 1; tc <= T ; tc++){
			max = Integer.MIN_VALUE; 
			min = Integer.MAX_VALUE;
			N = Integer.parseInt(br.readLine());
			num = new int[N];
			
			st = new StringTokenizer(br.readLine());
			int[] op = {Integer.parseInt(st.nextToken()),Integer.parseInt(st.nextToken()),Integer.parseInt(st.nextToken()),Integer.parseInt(st.nextToken())};
			
			st = new StringTokenizer(br.readLine());
			for(int n = 0; n < N; n++) {
				num[n] = Integer.parseInt(st.nextToken());
			}
			
			dfs(num[0], 1, op[0], op[1], op[2], op[3]);
			
			answer = max-min;
			
			sb.append("#").append(tc).append(" ").append(answer).append("\n");
		}
		
		System.out.println(sb);
	}
	
	static void dfs(int result, int count, int plus, int minus, int multiple, int divide) {
		
		if(count == N) {
			if(result < min) {
				min = result;
			}
			
			if(result > max) {
				max = result;
			}
		}
		
		if(plus > 0) {
			dfs(result + num[count], count+1, plus-1, minus, multiple, divide);
		}
		if(minus > 0) {
			dfs(result - num[count], count+1, plus, minus-1, multiple, divide);
		}
		if(multiple > 0) {
			dfs(result * num[count], count+1, plus, minus, multiple-1, divide);
		}
		if(divide > 0) {
			dfs(result / num[count], count+1, plus, minus, multiple, divide-1);
		}
		
	}
}

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

시뮬레이션의 정수를 담은 문제입니다.

주어진 문제의 조건과 순서를 따라 잘 구현하면 되지만 잘 구현하는것이 어렵습니다.

코드의 가독성을 높이기 위해 여러 단계를 나누어 함수로 구현하고

실행 시간을 줄이기 위해 재귀함수를 이용해서 이전 상태를 기억해 거기서부터 다시 탐색합니다.

상태를 기억할때는 Map이 2차원 배열임을 감안해 깊은 복사를 위해 copy() 함수를 따로 만들었습니다.

Java언어에서 N차원 배열로 모든 배열을 순회하며 복사해도 되지만 clone() 메소드가 Array에 존재해 활용했습니다.

모든 경우를 탐색해야하기 때문에 효율적인 코드를 짜는게 중요할 것 같습니다.

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;

public class q5656_SWEA_벽돌깨기 {
	static StringTokenizer st;
	static StringBuilder sb = new StringBuilder();
	static int answer, N, W, H;
	static int[][] delta = { { -1, 0 }, { 1, 0 }, { 0, -1 }, { 0, 1 } };
	static int[][] map;

	public static void main(String[] args) throws NumberFormatException, IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

		int T = Integer.parseInt(br.readLine());

		for (int tc = 1; tc <= T; tc++) {
			answer = Integer.MAX_VALUE;
			st = new StringTokenizer(br.readLine());
			N = Integer.parseInt(st.nextToken());
			W = Integer.parseInt(st.nextToken());
			H = Integer.parseInt(st.nextToken());

			map = new int[H][W];
			for (int h = 0; h < H; h++) {
				st = new StringTokenizer(br.readLine());
				for (int w = 0; w < W; w++) {
					map[h][w] = Integer.parseInt(st.nextToken());
				}
			}

			dfs(0);

			sb.append("#").append(tc).append(" ").append(answer).append("\n");
		}

		System.out.println(sb);
	}

	static void dfs(int count) {
		if (count == N) {
			answer = Math.min(answer, countBlock(map));
			return;
		}
		int[][] save = new int[H][W];
		for (int w = 0; w < W; w++) {		
			copy(map, save);				
			shoot(w);
			dfs(count + 1);
			copy(save, map);

		}
	}

	static boolean isIn(int x, int y) {
		if (0 <= x && x < H && 0 <= y && y < W) {
			return true;
		}

		return false;
	}

	static void copy(int[][] from, int[][] to) {
		for (int h = 0; h < H; h++) {
			to[h] = from[h].clone(); 
		}
	}

	static int countBlock(int[][] result) {
		int count = 0;
		for (int h = 0; h < H; h++) {
			for (int w = 0; w < W; w++) {
				if (result[h][w] != 0) {
					count++;
				}
			}
		}
		return count;
	}

	static void shoot(int w) {			
		for (int h = 0; h < H; h++) {	
			if (map[h][w] != 0) {		
				boom(h, w);
				return;
			}
		}
		return;
	}

	static void boom(int x, int y) {
		Queue<int[]> queue = new LinkedList<>();
		queue.offer(new int[] { x, y, map[x][y]-1 });
		map[x][y] = 0;

		while (!queue.isEmpty()) {
			int[] now = queue.poll();
			int range = now[2];

			for (int i = 0; i < 4; i++) {
				int nX = now[0];
				int nY = now[1];
				for (int r = 0; r < range; r++) {
					nX += delta[i][0];
					nY += delta[i][1];
					if (isIn(nX, nY) && map[nX][nY] != 0) {
						queue.offer(new int[] { nX, nY, map[nX][nY]-1 });
						map[nX][nY] = 0;
					}
				}
			}
		}

		gravity();
	}

	static void gravity() {
		Queue<Integer> queue;

		for (int w = 0; w < W; ++w) {   
			queue = new LinkedList<>();	

			for (int h = H - 1; h >= 0; --h) {
				if (map[h][w] > 0) {
					queue.offer(map[h][w]);
				}
			}

			for (int h = H - 1; h >= 0; --h) {
				if (!queue.isEmpty()) {
					map[h][w] = queue.poll();
				} else {
					map[h][w] = 0;
				}
			}
		}

	}
}

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

넓은 범위의 소수를 모두 구하는 '에라토스테네스의 채'를 응용한 문제입니다.

에라토스테네스의 채를 구현하는 방법을 알면 큰 어려움 없이 풀이할 수 있습니다.

이번 문제처럼 여러번 소수를 사용하는 문제에서도 필요한 범위의 소수를 미리 구해놓고 정답체크를 진행하면 매번 새로 소수를 구하는 것보다 좋은 성능을 얻을 수 있습니다. 

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

public class q4698Re_SWEA_테네스의특별한소수 {
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st;
		int T = Integer.parseInt(br.readLine());
		StringBuilder sb = new StringBuilder();

		int[] arr = new int[1_000_001];

		arr[1] = 1;

		for (int i = 2; i <= 1_000_000; i++) {
			if (arr[i] == 0) {
				for (int j = i * 2; j <= 1_000_000; j += i) {
					arr[j] = 1;
				}
			}
		}

		for (int t = 1; t <= T; t++) {
			st = new StringTokenizer(br.readLine());
			int D = Integer.parseInt(st.nextToken());
			int A = Integer.parseInt(st.nextToken());
			int B = Integer.parseInt(st.nextToken());
			int cnt = 0;

			for (int i = A; i <= B; i++) {
				if (arr[i] == 0) {
					if (String.valueOf(i).contains(String.valueOf(D))) {
						cnt++;
					}
				}
			}

			sb.append("#").append(t).append(" ").append(cnt).append("\n");
		}

		System.out.println(sb);
	}
}

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

주어진 조건에 맞게 양팔저울에 추를 올리는 경우의 수를 구하는 문제입니다.

Java의 경우에는 모든 경우에 대해 순열을 구하고 그 순열이 조건에 적합한지 검증을 하면서 가지치기를 해도 주어진 실행시간 안에 통과가 되지만, 조금 더 효율적으로 코드를 짤 수 있는 방법들이 있어 3가지를 전부 소개해드리겠습니다.

우선 기본적으로 모든 순열을 만들고, 이후 조건에 맞는 경우를 찾는 코드입니다.

시간 초과를 방지하기 위해 좌측의 무게가 절반을 넘어서는 경우 이후의 경우는 검증하지 않고 2^(N-현재 단계)만큼 더해주었습니다.

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

public class q3234_SWEA_준환이의양팔저울 {
	static StringTokenizer st;
	static StringBuilder sb = new StringBuilder();
	static int N, answer, total;
	static Integer[] gram;

	public static void main(String[] args) throws NumberFormatException, IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

		int T = Integer.parseInt(br.readLine());

		for (int tc = 1; tc <= T; tc++) {
			N = Integer.parseInt(br.readLine());
			answer = 0;
			total = 0;
			gram = new Integer[N];

			st = new StringTokenizer(br.readLine());
			for (int n = 0; n < N; n++) {
				gram[n] = Integer.parseInt(st.nextToken());
				total += gram[n];
			}
			total /= 2;

			makePermutation(0, new int[N], new boolean[N]);

			sb.append("#").append(tc).append(" ").append(answer).append("\n");
		}

		System.out.println(sb);
	}

	static void makePermutation(int count, int[] choosed, boolean[] visited) {
		if (count == N) {
			check(1, choosed, choosed[0], 0);
			return;
		}
		for (int i = 0; i < N; i++) {
			if (!visited[i]) {
				visited[i] = true;
				choosed[count] = gram[i];
				makePermutation(count + 1, choosed, visited);
				visited[i] = false;
			}
		}
	}

	static void check(int count, int[] choosed, int left, int right) {
		if (count == N) {
			answer++;
			return;
		}
		if (total < left) {
			int num = 1;
			for (int i = 0; i < N - count; i++) {
				num *= 2;
			}
			answer += num;
			return;
		}

		if (left >= right + choosed[count]) {

			check(count + 1, choosed, left, right + choosed[count]);
		}
		check(count + 1, choosed, left + choosed[count], right);

	}
}

두 번째론 모든 순열을 만들지 않고, 순열을 만드는 과정 안에 조건에 따른 검증을 넣어서 가지치기한 코드입니다.

마찬가지로 시간 초과를 방지하기 위해 좌측의 무게가 절반을 넘어서는 경우 이후의 경우는 검증하지 않고, (N-현재 단계)! * 2^(N-현재 단계)만큼 더해주었습니다.

순열이 다 만들어지지 않았기 때문에 경우의 수를 계산할 때 남은 추의 개수 팩토리얼까지 곱해주어야 합니다.

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

public class q3234_SWEA_준환이의양팔저울Re {
	static StringTokenizer st;
	static StringBuilder sb = new StringBuilder();
	static int N, answer, total;
	static Integer[] gram;

	public static void main(String[] args) throws NumberFormatException, IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

		int T = Integer.parseInt(br.readLine());

		for (int tc = 1; tc <= T; tc++) {
			N = Integer.parseInt(br.readLine());
			answer = 0;
			total = 0;
			gram = new Integer[N];

			st = new StringTokenizer(br.readLine());
			for (int n = 0; n < N; n++) {
				gram[n] = Integer.parseInt(st.nextToken());
				total += gram[n];
			}
			total /= 2;

			makePermutation(0, new boolean[N], 0, 0);

			sb.append("#").append(tc).append(" ").append(answer).append("\n");
		}

		System.out.println(sb);
	}

	static void makePermutation(int count, boolean[] visited, int left, int right) {
		// System.out.println(count + "선택됨," + left + " : " + right);

		if (count == N) {
			answer++;
			return;
		}

		if (total < left) {
			int num = 1;
			for (int i = 1; i <= N - count; i++) {
				num *= 2;
				num *= i;
			}
			answer += num;
			return;
		}

		for (int i = 0; i < N; i++) {
			if (!visited[i]) {
				visited[i] = true;
				makePermutation(count + 1, visited, left + gram[i], right);
				if (right + gram[i] <= left) {
					makePermutation(count + 1, visited, left, right + gram[i]);
				}
				visited[i] = false;
			}
		}
	}
}

세 번째로 메모이제이션을 활용해서 이미 탐색한 경우를 스킵한 코드입니다.

어떤 방법으로든 추의 위치 배정이 똑같은 시점이 오면 이후의 경우의 수의 개수는 같아집니다.

예를 들어 1,2,8,... 의 무게를 가진 추가 주어졌을때, 8(좌) → 1(우) → 2(우) 경우나 8(좌) → 2(우) → 1(우) 경우나 추의 현재 상태는 같습니다.

추의 상태가 같으면 이후 가능한 경우의 수도 같아집니다.

추의 상태를 사용한 추 (갯수가 작기 때문에 비트 마스킹으로 기록), 좌측에 놓인 무게로 저장하고 이전에 탐색한 적이 있다면 더 탐색을 하지 않고 그 값을 사용하는 코드입니다.

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

public class q3234_SWEA_준환이의양팔저울Re2 {
	static StringTokenizer st;
	static StringBuilder sb = new StringBuilder();
	static int N, total;
	static int[] gram;
	static int[][] memo;

	public static void main(String[] args) throws NumberFormatException, IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

		int T = Integer.parseInt(br.readLine());

		for (int tc = 1; tc <= T; tc++) {
			N = Integer.parseInt(br.readLine());
			total = 0;
			gram = new int[N];

			st = new StringTokenizer(br.readLine());
			for (int n = 0; n < N; n++) {
				gram[n] = Integer.parseInt(st.nextToken());
				total += gram[n];
			}

			memo = new int[total + 1][1 << N];

			sb.append("#").append(tc).append(" ").append(makePermutation(0, 0, 0, 0)).append("\n");
		}

		System.out.println(sb);
	}

	static int makePermutation(int count, int bitmask, int left, int right) {
		if (count == N) {
			return 1;
		}

		int sum = memo[left][bitmask];

		if (sum == 0) {
			for (int i = 0; i < N; i++) {
				if ((bitmask & (1 << i)) == 0) {
					sum += makePermutation(count + 1, bitmask | (1 << i), left + gram[i], right);
					if (right + gram[i] <= left) {
						sum += makePermutation(count + 1, bitmask | (1 << i), left, right + gram[i]);
					}
				}
			}
			return memo[left][bitmask] = sum;
		}
		return sum;
	}
}

위에서부터 순서대로 메모이제이션 → 순열구하면서 가지치기 → 순열 구하고 가지치기 코드의 실행결과입니다.

여러가지로 생각할 거리가 많은 좋은 문제였습니다.

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

문제 자체는 기본적인 DFS 백트래킹을 사용해서 풀 수 있는 문제입니다.

하지만 가지치기에 따라 실행시간이 큰 차이를 보였습니다.

생각해보면 문제에서 주어진 테스트케이스의 조건에서, R과 C의 크기가 1 이상 20 이하입니다.

즉 최대 400칸의 맵이 주어지는 건데 알파벳의 개수는 26개로 제한되어있기 때문에 가지치기를 통해 자르지 않는 경우 생각보다 훨씬 더 많은 추가 탐색이 실행될 걸 알 수 있습니다.

가지치기의 아이디어는 간단합니다.

가능한 최대값을 이미 정답으로 가지고 있는 경우, answer = 26인 경우 더이상의 탐색을 하지않고 재귀를 끝내면 됩니다.

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

public class q7699_SWEA_수지의수지맞는여행 {
	static StringTokenizer st;
	static StringBuilder sb = new StringBuilder();
	static int R, C, answer;
	static int[][] map;
	static boolean[] visit;
	static int[][] delta = { { -1, 0 }, { 1, 0 }, { 0, -1 }, { 0, 1 } };

	public static void main(String[] args) throws NumberFormatException, IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

		int T = Integer.parseInt(br.readLine());

		for (int tc = 1; tc <= T; tc++) {
			answer = 0;
			st = new StringTokenizer(br.readLine());
			R = Integer.parseInt(st.nextToken());
			C = Integer.parseInt(st.nextToken());

			map = new int[R][C];
			visit = new boolean[26];

			for (int r = 0; r < R; r++) {
				String input = br.readLine();
				for (int c = 0; c < C; c++) {
					map[r][c] = input.charAt(c) - 'A';
				}
			}
			visit[map[0][0]] = true;
			dfs(0, 0, 1);

			sb.append("#").append(tc).append(" ").append(answer).append("\n");
		}

		System.out.println(sb);
	}

	static void dfs(int x, int y, int count) {
		if (answer == 26) {
			return;
		}
		answer = Math.max(answer, count);

		for (int i = 0; i < 4; i++) {
			int nX = x + delta[i][0];
			int nY = y + delta[i][1];

			if (isIn(nX, nY)) {
				if (!visit[map[nX][nY]]) {
					visit[map[nX][nY]] = true;
					dfs(nX, nY, count + 1);
					visit[map[nX][nY]] = false;
				}
			}
		}
	}

	static boolean isIn(int x, int y) {
		if (0 <= x && x < R && 0 <= y && y < C) {
			return true;
		}
		return false;
	}
}

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

8458. 원점으로 집합과 비슷한 문제입니다.

상하좌우로 N칸을 움직여서 원하는 목적지로 가면 되지만 (상,하)와 (좌,우)를 연속으로 움직일 수 없고 번갈아가면서 움직여야합니다.

8458번과 비슷한 방식으로 접근할 수 있습니다.

내 위치와 목적지의 X좌표, Y좌표의 거리(절댓값)가 홀짝이 같은지에 따라 정답이 나뉩니다.

예를들어 내 위치가 (0,0)이고 목적지가 (2,4)처럼 X Y좌표 모두 짝수거리만큼 떨어져있다면,

상우상우로움직여 (2,2)위치로 이동하고,상 두번을 움직이기 위해 상 좌 상 우 이런식으로 좌우 움직임을 상쇄해서 도착하면 됩니다.

홀수의 경우에도 더 작은 거리를 0으로 만들만큼 움직이면, 남은 짝수 거리를 같은 방법으로 상쇄하여 도착합니다.

즉, X Y 거리가 모두 짝수거나 모두 홀수면 (둘 중 더 먼 거리 * 2배) 만큼 움직여서 목적지에 도착할 수 있습니다.

둘의 홀짝이 다르면 어떨까요?

내 위치가 (0,0)이고 목적지가 (2,3)이라면

상우상우로 움직여 (2,2)에 도착하고 바로 상으로 움직여 5번만에 목적지에 도착할 수 있습니다.

(우상우상으로 움직이면 도착을 못합니다)

이때는 (둘 중 더 먼 거리 * 2배) - 1 만큼 움직여서 목적지에 도착할 수 있습니다.

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

public class q8382_SWEA_방향전환 {
	static StringTokenizer st;
	static StringBuilder sb = new StringBuilder();

	public static void main(String[] args) throws NumberFormatException, IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

		int T = Integer.parseInt(br.readLine());
		int answer;

		for (int tc = 1; tc <= T; tc++) {
			st = new StringTokenizer(br.readLine());
			int aX = Integer.parseInt(st.nextToken());
			int aY = Integer.parseInt(st.nextToken());
			int bX = Integer.parseInt(st.nextToken());
			int bY = Integer.parseInt(st.nextToken());
			int x = Math.abs(aX - bX);
			int y = Math.abs(aY - bY);

			answer = Math.abs(x - y) % 2 == 0 ? 2 * Math.max(x, y) : 2 * Math.max(x, y) - 1;

			sb.append("#").append(tc).append(" ").append(answer).append("\n");
		}

		System.out.println(sb);
	}
}

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

(문제에서 주어진 조건설명이 살짝 부족한 문제여서 혼동의 여지가 많습니다.)

원점에서 각기 다른 거리만큼 떨어져 있는 점들은 1... N칸씩 움직여서 모두가 원점에 도착하게 하는 게 목표입니다.

이때 N칸은 상하좌우 어느 방향으로든 나누어 움직일 수 있습니다.

(N이 3칸일때 상상좌 상하상 이런 식으로 움직일 수 있습니다. 단, 자기 자리에서 움직이지 않는 건 안됩니다.)

가만히 생각해보면 원점에 먼저 도착한 점들은 원점에서 진동하듯 좌우로 움직이기만해도 된다는 걸 알 수 있습니다.

예를 들어서, N=3일때 원점에 도착한 점 A는 다음 N=4의 움직임에서 좌우좌우로 움직이면 그대로 원점입니다.

다만 이후 N=5일때 움직이면 어떻게 움직이던지 원점에서 한 칸 이상 나가게 됩니다.

여기서 아이디어를 얻어 우리는 홀짝을 이용해 점들이 원점에 모두 모일 수 있는지 없는지를 알 수 있습니다.

원점으로부터의 거리가 모두 홀수거나 모두 짝수면 어떤 N일 때 확실하게 원점으로 모일 수 있으나, 거리가 홀수와 짝수가 섞여 있다면 어떤 방법으로도 동시에 원점에 멈추는 게 불가능합니다.

점 A가 원점에서 한 칸, B가 두 칸 떨어진 테스트케이스가 있다고 해봅시다.

처음 N=1일때 점 A는 원점으로 들어갑니다. 점 B는 원점으로 향하지만 한 칸 떨어진 위치에 멈춥니다.

다음 N=2일때 점 A는 좌우로 움직여 그대로 원점에 남습니다. 점 B는 원점을 지나 다시 한 칸 떨어집니다.

N=3일땐 반대로 점 B가 원점에 들어가고 좌우로 움직여 원점에 남습니다. 하지만 점 A가 원점에서 나가게 됩니다.

어떤 방법으로도 점 A와 B가 둘 다 원점에 들어가게 할 수 없습니다.

이렇게 해결할 수 없는 경우를 걸러내고, 이제 몇 칸을 움직여야 원점에 들어갈 수 있는지를 계산해봅시다.

위에서 말했다시피 원점에 먼저 도착한 점들은 원점에서 왕복운동을 하면서 대기하면 됩니다.

즉 우리는 원점에서 가장 멀리있는 점만 생각하면 됩니다. 

가장 멀리있는 점이 원점으로 도착했을때도 분기가 나뉩니다.

예를들어 가장 멀리있던 점이 8칸 떨어져 있었다고 생각해봅시다.

N=1, N=2, N=3을 지나며 다른 점들은 원점에 도달해 왕복운동을 하며 대기합니다.

N=4일때 가장 멀리있던 점이 원점에 도착합니다. 하지만 두번의 움직임이 남습니다.

이 남은 움직임이 짝수라면, 먼저 도착한 점들과 같이 왕복운동을 해 소모하면 됩니다.

홀수라면, 다음 기회를 노려야합니다. 즉, 다시 한 번 홀수번 움직여 원점에 맞춰야합니다.

정리하면 

1. 점들이 모두 홀수거나 모두 짝수여야 원점에 모이는게 가능하다.

2. 가장 먼 점에서부터 N을 늘려가며 거리를 줄인다.

3. 가장 먼 점이 원점에 도착했을때, 남은 횟수가 짝수라면 바로 종료, 홀수라면 홀수번 움직여야 종료된다.

(원점에 도착했을때의 움직임이 짝수였다면 다음 홀수번으로, 원점에 도착했을때의 움직임이 홀수였다면 짝수,홀수번 2번의 움직임을 더 해야 종료할 수 있습니다.)

설명도 조금 미흡했고 이해하기도 어려웠던 원점으로집함 문제였습니다. 감사합니다.

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

public class q8458_SWEA_원점으로집합 {
	static StringTokenizer st;
	static StringBuilder sb = new StringBuilder();

	public static void main(String[] args) throws NumberFormatException, IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

		int T = Integer.parseInt(br.readLine());

		for (int tc = 1; tc <= T; tc++) {
			int answer = 0;
			boolean flag = false;
			int N = Integer.parseInt(br.readLine());

			st = new StringTokenizer(br.readLine());
			long X = Integer.parseInt(st.nextToken());
			long Y = Integer.parseInt(st.nextToken());
			long odd = (Math.abs(X) + Math.abs(Y)) % 2;
			long gap = Math.max(0, Math.abs(X) + Math.abs(Y));

			for (int n = 1; n < N; n++) {
				st = new StringTokenizer(br.readLine());
				X = Integer.parseInt(st.nextToken());
				Y = Integer.parseInt(st.nextToken());

				if ((Math.abs(X) + Math.abs(Y)) % 2 != odd) {
					flag = true;
				}

				gap = Math.max(gap, Math.abs(X) + Math.abs(Y));
			}

			if (flag) {
				sb.append("#").append(tc).append(" -1").append("\n");
			} else {

				while (gap > 0) {
					answer++;
					gap -= answer;
				}
				answer = gap % 2 == 0 ? answer : (answer % 2 == 0 ? answer + 1 : answer + 2);

				sb.append("#").append(tc).append(" ").append(answer).append("\n");
			}
		}

		System.out.println(sb);
	}
}