https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AWzaq5KKk_ADFAVU
SW Expert Academy
SW 프로그래밍 역량 강화에 도움이 되는 다양한 학습 컨텐츠를 확인하세요!
swexpertacademy.com
(문제에서 주어진 조건설명이 살짝 부족한 문제여서 혼동의 여지가 많습니다.)
원점에서 각기 다른 거리만큼 떨어져 있는 점들은 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);
}
}
'🔍 알고리즘 > SWEA' 카테고리의 다른 글
| [Java] SWEA 7699.수지의 수지맞는 여행 D4 (0) | 2022.07.04 |
|---|---|
| [Java] SWEA 8382.방향전환 D4 (0) | 2022.07.03 |
| [Java] SWEA 11112.다트게임 D3 (0) | 2022.07.01 |
| [Java] SWEA 11112.셀로판지 D4 (0) | 2022.06.30 |
| [Java] SWEA 10966.물놀이를 가자 D4 (0) | 2022.06.29 |
