BAEKJOON / 백준 - JAVA 31872번 강의실

2024.05.31기준 - 실버3

백준, BEAKJOON, BOJ, JAVA, 자바

 

풀이

이 문제는 혁준이가 학교에서 강의를 들어야 하는데, 모든 가의를 들었을때 걸리는 최소 시간을 구하는 문제입니다.

 

조건이 2가지 있습니다.

1. 왼쪽또는 오른쪽으로 1만큼 이동할 때마다 1초의 시간이 걸립니다.
2. 최대 K번 어디든 원하는 위치로 순간이동을 할 수 있습니다.

저의 접근은 강의실을 정렬을 한 뒤 굳이 다시 뒤로(왼쪽)으로 돌아갈 필요가 없다고 생각해 강의실과 강의실의 거리를 이용하여 문제에 접근했습니다.

 

1. 입력된 강의실 위치를 오름차순으로 정렬한다.
2. 정렬된 강의실 위치를 i, i + 1끼리 거리를 비교하여 새로운 배열에 적제한다.
3. 거리가 저장된 배열 중 뒤에서 k번 - 1까지 합을 계산하고 출력한다.

 

 

코드

package Main;

import java.io.*;
import java.util.*;

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));
		StringTokenizer st = new StringTokenizer(br.readLine());
		int n = Integer.parseInt(st.nextToken()); // 강의 개수
		int k = Integer.parseInt(st.nextToken()); // 순간이동 횟수
		
		int[] arr = new int[n];
		st = new StringTokenizer(br.readLine());
		for (int i = 0; i < n; i++) {
			arr[i] = Integer.parseInt(st.nextToken());
		}
		
		// 오름차순으로 정렬
		Arrays.sort(arr);
		
		// 각 강의실 마다 이동해야되는 거리를 저장
		int[] times = new int[n]; 
		int start = 0; // 혁준이 현재 위치
		
		for (int i = 0; i < n; i++) {
			times[i] = arr[i] - start;
			start = arr[i];
		}
		
		// 거리들 오름차순 정렬 
		Arrays.sort(times);
		
		int count = 0;
		
		// 순간이동 횟수만큼 먼 거리는 제거
		for (int i = 0; i < n - k; i++) {
			count += times[i];
		}
		
		bw.write(Integer.toString(count));
		bw.flush();
		bw.close();
		br.close();
	}
}