Problem Solving/Baekjoon
[백준] 15970 화살표 그리기 - Brute Force / Java
graycode
2023. 5. 29. 13:47
• 문제 링크
15970번: 화살표 그리기
직선 위에 위치를 나타내는 0, 1, 2, ...와 같은 음수가 아닌 정수들이 일정한 간격으로 오른쪽 방향으로 놓여 있다. 이러한 위치들 중 N개의 위치에 하나씩 점들이 주어진다(<그림 1>). 주어진 점들
www.acmicpc.net
• 풀이 과정
• 풀이 코드
import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.Arrays;
import java.util.StringTokenizer;
public class Main {
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
int n = Integer.parseInt(br.readLine());
Pair[] arr = new Pair[n];
for (int i = 0; i < n; i++) {
StringTokenizer st = new StringTokenizer(br.readLine());
arr[i] = new Pair(Integer.parseInt(st.nextToken()), Integer.parseInt(st.nextToken()));
}
Arrays.sort(arr);
int cnt = arr[0].color == arr[1].color ? arr[1].idx - arr[0].idx : 0;
cnt += arr[n - 1].color == arr[n - 2].color ? arr[n - 1].idx - arr[n - 2].idx : 0;
for (int i = 1; i < n - 1; i++) {
Pair cur = arr[i], left = arr[i - 1], right = arr[i + 1];
cnt += Math.min(cur.color == left.color ? cur.idx - left.idx : 1000000, cur.color == right.color ? right.idx - cur.idx : 1000000);
}
bw.write(String.valueOf(cnt));
bw.flush();
}
private static class Pair implements Comparable<Pair> {
int idx, color;
public Pair(int idx, int color) {
this.idx = idx;
this.color = color;
}
@Override
public int compareTo(Pair o) {
return this.color == o.color ? this.idx - o.idx : this.color - o.color;
}
}
}