[백준] 알고리즘 분류(그리디 알고리즘,JAVA)18310번, 안테나

문제 링크

18310번: 안테나

---

주의사항

• JAVA를 사용하여 프로그램을 사용하였습니다.
• 백준에서 코드를 작성하였을 때 아래 형태에서 Main에서 결과가 출력되어야 합니다.

public class Main{ 	
	public static void main(String[] args){
    }
}

---

문제 설명

---

접근 방법

이 문제에 핵심

 

1. 안테나는 집이 위치한 곳에 설치할 수 있습니다.

2. 안테나로부터 모든 집까지의 거리의 총합이 최소값을 결과로 출력합니다.

3. 안테나를 설치할 수 있는 위치값이 여러 개일 경우 가장 작은 값을 출력합니다.

 

알고리즘 진행 순서.

 

1. 입력된 정보를 저장합니다.

 

2. 집의 위치 기준 정렬한 뒤, 중간에 안테나를 설치해서 거리를 구합니다.

 

3. 중간에 설치한 안테나의 거리 총합을 결과로 출력합니다.

 

 

중간에 안테나 설치하기!

 

※중간에 안테나를 설치하는 이유는 각 거리의 차가 최소가 되려면 중간값이 되어야 하기 때문입니다.

 

 

 

집의 개수가 홀수일 때

 

중간 위치 : N/2

 

예를 들어.

 

1 2 3 4 5 일 때

 

중간값 : 3

 

집의 개수가 짝수일 때

 

중간 위치 : N/2, N/2 - 1

 

예를 들어.

 

1 2 3 4 일 때

 

중간값 : 2, 3

 

 

예제입력 1.

 

1. 입력된 정보를 저장합니다.

 

N = 4

 

집의 위치

집 1	집 2	집 3	집 4
5	1	7	9

 

2. 집의 위치 기준 정렬한 뒤, 중간에 안테나를 설치해서 거리를 구합니다.

 

집의 위치 기준 오름차순 정렬!

 

집 2	집 1	집 3	집 4
1	5	7	9

 

 

집의 개수 : 4(짝수)

 

중간값 : 집1(N/2-1), 집 3(N/2)

 

중간에 안테나 설치해서 거리 총합 구하기

 

집1 안테나 설치할 때

(5 - 1) + (5 - 5) + (7 - 5) + (9 - 5) = 4 + 0 + 2 + 4 = 10

거리의 총합 : 10

 

집2 안테나 설치할 때

(7 - 1) + (7 - 5) + (7 - 7) + (9 - 7) = 6 + 2 + 0 + 2 = 10

거리의 총합 : 10

 

3. 중간에 설치한 안테나의 거리 총합을 결과로 출력합니다.

거리의 총합 : 10

 

10을 결과로 출력합니다.

 

• BufferedReader를 사용하여 입력되는 정보를 저장합니다.
• StringTokenzier를 이용하여 집에 위치 정보를 띄어쓰기 기준 나누었습니다.
• Arrays.sort를 이용해서  집의 위치 기준 오름차순 정렬하였습니다.
• 집의 개수에 따른 중간 위치에 안테나를 설치하여 거리의 총합 최소값을 구합니다.
• 안테나를 설치한 위치를 결과로 BufferedWriter에 저장하였습니다.
• BufferedWriter에 저장된 결과값을 출력하였습니다.

 

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

public class Main{
    public static void main(String[] args) throws IOException {
        //입력값 처리하는 BufferedReader
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        //결과값 출력하는 BufferedWriter
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        int N = Integer.parseInt(br.readLine());
        StringTokenizer st = new StringTokenizer(br.readLine()," ");
        int[] arr = new int[N];
        //집의 위치 정보 저장
        for(int i=0;i<N;i++)
            arr[i] = Integer.parseInt(st.nextToken());
        Arrays.sort(arr);	//오름차순 정렬
        int mid = N/2;	//중간값
        //집의 개수가 짝수일 때
        if(N % 2 == 0){
            //N/2에 안테나 설치시 거리의 총합 구하기
            int sum1 = 0;
            for(int i=0;i<N;i++)
                sum1 += Math.abs(arr[i] - arr[mid]);
            //N/2 - 1에 안테나 설치시 거리의 총합 구하기
            int sum2 = 0;
            mid--;
            for(int i=0;i<N;i++)
                sum2 += Math.abs(arr[i] - arr[mid]);
            //거리의 총합이 더 큰 곳에 안테나 설치!
            if(sum1 > sum2)
                mid++;
        }
        bw.write(arr[mid] + "");	//안테나 설치한 위치 BufferedWriter 저장
        bw.flush();		//결과 출력
        bw.close();
        br.close();
    }
}