문제 출처 - SW Expert Academy
문제는 여기
[문제]
N개의 격자점이 있다.
이 점들을 몇 번 움직여 모든 점을 원점((0, 0))으로 이동시키고 싶다.
한 번의 움직임은 모든 점을 움직이게 하고,
i번째 움직임에서 각 점은 상하좌우로 i만큼의 거리를 반드시 이동해야 한다.
최소 몇 번의 움직임으로 모든 점을 원점에 모을 수 있는지 구하는 프로그램을 작성하라.
[입력]
첫 번째 줄에 테스트 케이스의 수 T가 주어진다.
각 테스트 케이스의 첫 번째 줄에는 하나의 정수 N(1 ≤ N ≤ 10)이 주어진다.
다음 N개의 줄의 i번째 줄에는 두 정수 xi, yi(-109 ≤ xi, yi ≤ 109)가 공백 하나로 구분되어 주어진다.
이는 i번째 점이 (xi, yi)에 위치함을 나타낸다.
[출력]
각 테스트 케이스마다 ‘#x’(x는 테스트 케이스 번호를 의미하며 1부터 시작한다)를 출력하고,
각 테스트 케이스마다 최소 몇 번 움직여야 모든 점이 원점에 모이는지 출력한다.
만약 모든 점을 원점으로 이동시킬 수 없으면, -1을 출력한다.
[풀이]
1. 먼저 입력되는 값들의 좌표를 해당 군으로 맞춰준다.
2. 군들이 홀수인지 짝수인지 체크해준다.
3. 군들의 최고값을 구한다.
4. 최고값을 기준으로 1부터 i값을 늘려가며 누적 합을 구한다.
5. 최고값이 누적 합보다 작고 누적합 - 최고값이 짝수일 때 결과를 출력한다.
[접근]
1. (x, y)의 값을 (x, 0) 혹은 (0, y)처럼 한 직선 위로 옮겨서 생각한다.
2. 누적 합의 값이 짝수일 때는 짝수만큼만 이동이 가능하고 홀수일 때는 홀수로만 이동이 가능하다.
3. 주어지는 값들의 홀수, 짝수의 유무가 일치되지 않는다면 무조건 불가능하다.
4. 누적합 - 최고값이 짝수 값일 때 결과를 출력하는 이유는 짝수 - 짝수 or 홀수 - 홀수 일 때 짝수이기 때문이다.
[코드]
package swet;
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.StringTokenizer;
public class Solution_D4_8458 {
static int T;
static int n;
static int[] x; // 각 x좌표를 받기위한 배열
static int[] y; // 각 y좌표를 받기위한 배열
static int result; // 결과값 변수
static boolean[] odd; // 홀수인지를 저장하기 위한 배열
public static void main(String[] args) throws Exception {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
T = Integer.parseInt(br.readLine());
start :
for (int t = 1; t <= T; t++) {
n = Integer.parseInt(br.readLine());
x = new int[n];
y = new int[n];
odd = new boolean[n];
Arrays.fill(odd, false); // 모든 값을 false로 초기화
result = 0;
long max = Integer.MIN_VALUE;
for (int i = 0; i < n; i++) {
StringTokenizer st = new StringTokenizer(br.readLine());
x[i] = Integer.parseInt(st.nextToken());
y[i] = Integer.parseInt(st.nextToken());
int goon = Math.abs(x[i]) + Math.abs(y[i]); // 절대값으로 구해 최고값을 매겨준다
// 3,1일때와 4,0일때의 결과값은 동일하기 때문에
// x,y의 좌표로 두지 않고 한 직선 위에 오도록 해준다.
max = Math.max(max, goon); // 최고값을 저장
if (goon % 2 == 1) // 홀수인지 짝수인지 체크
odd[i] = true;
}
// 만약 전부 다 짝수거나 홀수가 아니면 불가능하다.
boolean check = odd[0];
for (int i = 1; i < n; i++) {
if (check != odd[i]) { // 만약에 처음의 값과 다른 값이 나온다면
System.out.println("#" + t + " -1"); // -1을 출력해주고
continue start; // 시작으로 이동한다.
}
}
int i = 1;
int sum = 0; // 누적합 변수
while (true) {
// sum의 값이 짝수일때는 짝수로만 이동 가능하고, 홀수일때는 홀수로만 이동 가능
// max값보다 합이 크고 |max - sum|의 값이 짝수일 때
if (sum >= max && Math.abs(sum - max) % 2 == 0)
break;
sum += i;
i++;
result++;
}
System.out.println("#" + t + " " + result);
}
}
}
'문제 풀이 > SW expert academy' 카테고리의 다른 글
[SWEA] 모의 SW 역량테스트 1953번 탈주범 검거 (JAVA) (0) | 2021.10.01 |
---|---|
[SWEA] 모의 SW 역량테스트 4014번 활주로 건설 (JAVA) (0) | 2021.10.01 |
[SWEA] 모의 SW 역량테스트 1949번 등산로 조성 (JAVA) (0) | 2021.09.30 |
[SWEA] D4 1249번 보급로 (JAVA) (0) | 2021.09.30 |
[SWEA] D4 8382번 방향 전환 (JAVA) (0) | 2021.09.30 |