[Baekjoon] 29891_체크포인트 달리기

Silver IV

문제(출처: https://www.acmicpc.net/problem/29891)

---

< 체크포인트 달리기 >

 

문제 풀이 

 

체크포인트 위치를 음수와 양수로 나눠서 계산한다. 이동 거리를 최소화할 수 있는 방법은 가장 멀리 있는 체크포인트 위치부터 체크하는 것이다.

 

 

 my solution (Java)

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

public class _29891_ { // 체크포인트 달리기

	public static void main(String[] args) throws IOException {
		BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(bf.readLine());

		int n = Integer.parseInt(st.nextToken());
		int k = Integer.parseInt(st.nextToken());

		ArrayList<Integer> list1 = new ArrayList<>();
		ArrayList<Integer> list2 = new ArrayList<>();
		for (int i = 0; i < n; i++) {
			int num = Integer.parseInt(bf.readLine());
			if (num < 0) {
				list1.add(num);
			} else {
				list2.add(num);
			}
		}

		Collections.sort(list1);
		Collections.sort(list2, Collections.reverseOrder());

		long result = 0;
		int cnt = 0;
		for (int i = 0; i < list1.size(); i++) {
			if (cnt == 0) {
				result += Math.abs(list1.get(i)) * 2;
				cnt += 1;
			} else if (cnt < k) {
				cnt += 1;
			}

			if (cnt == k) {
				cnt = 0;
			}
		}

		cnt=0;
		for (int i = 0; i < list2.size(); i++) {
			if (cnt == 0) {
				result += list2.get(i) * 2;
				cnt += 1;
			} else if (cnt < k) {
				cnt += 1;
			}

			if (cnt == k) {
				cnt = 0;
			}
		}
		System.out.println(result);
	}
}

변수)
n, k : 체크포인트 개수, 한 번에 체크할 수 있는 체크포인트 개수
list1, list2 : 음수, 양수 체크포인트 위치
result : 이동 거리
cnt : 체크한 체크포인트 개수

 

체크포인트 개수와 한 번에 체크할 수 있는 체크포인트 개수를 입력받는다. 체크포인트 위치를 입력받으면서 음수와 양수를 나눠 각 ArrayList에 저장한다. 음수가 저장된 ArrayList를 오름차순으로 정렬하고 양수가 저장된 ArrayList를 내림차순으로 정렬한다.

 

각각 음수와 양수가 저장된 ArrayList를 순환한다. 하나도 체크를 하지 않았다면 체크를 하고 result에 왕복 거리를 더한다. 만약 이미 체크한 적이 있으며 k보다 작다면 체크 표시만 한다. 체크한 개수가 k와 일치하다면 한 번에 체크할 수 있는 만큼 다한 것이므로 체크 개수를 0으로 초기화한다.  

 

최종 result를 출력한다.

---

---