[백준, Java] 1637번, 작은 벌점(이분 탐색)

문제 링크

16498번: 작은 벌점

---

주의사항

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

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

---

문제 설명

---

접근 방법

이 문제에 핵심

1. 세 명의 플레이어는 각자 정수가 적힌 카드들을 가지고 있습니다.

2. 3개의 카드가 놓여졌을 때 문제에 점화식에 따라 벌점을 구할 수 있습니다.

3. 구할 수 있는 최소 벌점을 결과로 출력합니다.

 

알고리즘 진행 순서.

 

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

 

2. 이분탐색을 이용한 완전탐색을 진행하여 최소 벌점을 탐색합니다.

 

3. 탐색이 끝난 뒤 구한 최소 벌점을 결과로 출력합니다.

 

 

완전 탐색, 이분탐색

 

완전탐색은 첫 번 째 플레이어가 고른 카드를 기준으로 모든 경우를 탐색합니다.

 

 

위 점화식에 최소값이 나오려면

 

a, b, c에서 최대값과 최소값의 차이가 최소가 되어야 합니다.

 

최소가 되어야 한다는 것을 기준으로 이분탐색을 진행합니다.

첫 번째 플레이어가 고른 수에서 가장 차이가 적은 수를 두 번째 플레이어가 선택합니다.

 

이후 세 번째 플레이어는 첫 번째 또는 두 번째 플레이어의 카드와 가장 근접한 수를 선택해야 합니다.

 

즉, 식으로 표현하면

 

 

첫 번째 플레이어 카드 : a일 때

 

두 번째 플레이어 카드 : b(a와 가장 가까운 수)

 

세 번째 플레이어 카드 : c(a와 가장 가까운 수, b와 가장 가까운 수 중에서 점화식이 더 작은 값)

 

위 과정을 완전탐색을 통해서 최소 벌점을 구하면 됩니다.

 

 

예제입력 1.

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

 

A : 5

 

B : 3

 

C : 4

 

 

A	1	4	5	8	10
B	6	9	15
C	2	3	6	6

 

2. 이분탐색을 이용한 완전탐색을 진행하여 최소 벌점을 탐색합니다.

A = 1일 때

 

B = 6

 

C = 2(A에 가까운 수, 점화식 값 : 5), 6(B에 가까운 수, 점화식 값 : 5)

 

....

 

 

A = 5일 때

 

B = 6

 

C = 6(A에 가까운 수, 점화식 값 : 1), 6(B에 가까운 수, 점화식 값 : 1)

 

 

 

....

 

3. 탐색이 끝난 뒤 구한 최소 벌점을 결과로 출력합니다.

 

최소 벌점 1을 결과로 출력합니다.

 

 

 

 

• BufferedReader를 사용하여 입력되는 정보를 저장합니다.
• StringTokenizer를 이용하여 카드의 정보를 띄어쓰기 기준 구분합니다.
• 첫 번째 플레이어가 선택한 카드를 기준으로 완전탐색을 진행합니다.
• search함수를 통해서 벌점이 최소가 되도록 하는 이분탐색을 진행합니다.
• 완전 탐색을 끝난 뒤 최소 벌점을 BufferedWriter 저장합니다.
• BufferedWriter에 저장된 결과를 출력합니다.

• search함수는 이분탐색을 통해서 가장 가까운 수를 찾는 함수입니다.
• check함수는 가장 가까운 수가 맞는지 확인하는 함수입니다.

 

결과코드

import java.util.*;
import java.io.*;
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));
        StringTokenizer st = new StringTokenizer(br.readLine()," ");
        //플레이어 카드 개수 저장 배열
        int[] ABC = new int[3];
        for(int i=0;i<3;i++){
            ABC[i] = Integer.parseInt(st.nextToken());
        }
        //플레이어 카드 정보 저장
        int[] A = new int[ABC[0]];
        int[] B = new int[ABC[1]];
        int[] C = new int[ABC[2]];
        st = new StringTokenizer(br.readLine()," ");
        for(int i=0;i<ABC[0];i++){
            A[i] = Integer.parseInt(st.nextToken());
        }
        st = new StringTokenizer(br.readLine()," ");
        for(int i=0;i<ABC[1];i++){
            B[i] = Integer.parseInt(st.nextToken());
        }
        st = new StringTokenizer(br.readLine()," ");
        for(int i=0;i<ABC[2];i++){
            C[i] = Integer.parseInt(st.nextToken());
        }
        //이분 탐색을 위해 B와 C는 오름차순 정렬
        Arrays.sort(B);
        Arrays.sort(C);
        //결과값 변수
        int result = Integer.MAX_VALUE;
        //첫 번째 플레이어 카드 선택 기준 완전 탐색 진행
        for(int i=0;i<ABC[0];i++){
            //나올 수 있는 최소 벌점이 이미 나왔을 때
            if(result == 0){
                break;
            }
            
            int sA = A[i];
            //두 번째 플레이어 카드 선택
            int sB = search(sA, B);
            //세 번째 플레이어 A와 가장 가까운 카드 선택
            int sC1 = search(sB, C);
            //세 번째 플레이어 B와 가장 가까운 카드 선택
            int sC2 = search(sA, C);

            //세 번째 플레이어가 A와 가까운 카드일 때 벌점 계산
            int max = Math.max(sA, Math.max(sB, sC1));
            int min = Math.min(sA, Math.min(sB, sC1));
            result = Math.min(result, Math.abs(max-min));

            //세 번째 플레이어가 B와 가까운 카드일 때 벌점 계산
            max = Math.max(sA, Math.max(sB, sC2));
            min = Math.min(sA, Math.min(sB, sC2));
            result = Math.min(result, Math.abs(max-min));
        }
        //최소 벌점 BufferedWriter 저장
        bw.write(String.valueOf(result));
        bw.flush();		//결과 출력
        bw.close();
        br.close();
    }
    //가장 가까운 값 찾는 이분탐색 함수
    static int search(int select, int[] arr){
        int left = 0;
        int right = arr.length-1;
        int mid = (left + right)/2;
        //현재 최소 차이 값
        int nearest = arr[mid];
        //이분탐색 시작
        while(left <= right){
            mid = (left+right)/2;
            if(arr[mid] == select){
                return select;
            }
            else if(arr[mid] < select){
                left = mid+1;
            }
            else{
                right = mid-1;
            }
            //가장 가까운 값인지 비교
            if(check(arr[mid], nearest, select)){
                nearest = arr[mid];
            }
        }
        //가장 가까운 값 반환
        return nearest;
    }
    //가장 가까운 값인지 확인하는 함수
    public static boolean check(int num, int near, int t) {
        return Math.abs(num - t) < Math.abs(near - t);
    }
}