[백준] 단계별로 풀어보기(단계:21,이분 탐색,JAVA)1654번, 랜선 자르기

문제 링크

1654번: 랜선 자르기

---

주의사항

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

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

---

문제 설명

---

접근 방법

이분 탐색이란 오름차순으로 정렬된 값들에서 특정한 값을 찾는 과정입니다.

중간 값을 임의의 값으로 설정하여 찾는 값과 비교하여 동일하면 찾는 값이 되고 크면 시작값이 임의의 값이 되고 작으면 최대값이 임의의 값이 되어 그 과정을 반복하여 찾는 값이 정렬된 값에 존재하는지 확인하는 방법입니다.

이분탐색에 자세한 내용은 링크를 남기겠습니다.

이진 검색 알고리즘 - 위키백과, 우리 모두의 백과사전

예를들어(시작값 = 1, 최대값 = 9)

찾는 값 = 3, 중간값 = 5

1. 찾는 값이 중간 값보다 작으므로 최대값은 4가 된다.

1

2

3

4

5

6

7

8

9

시작값 = 1, 최대값 = 4 찾는값 = 3 중간값 = 2

2. 찾는 값이 중간 값보다 크므로 시작값은 = 3

1

2

3

4

5

6

7

8

9

시작값 = 3, 최대값 = 4 찾는값 = 3 중간값 = 33. 찾는 값과 중간값이 같으므로 3은 정렬된 숫자에 존재합니다.

1

2

3

4

5

6

7

8

9

이 문제에서는 이분 탐색을 이용해서 얻은 중간값으로 랜선들을 나누었을 때 개수가 필요한 랜선의 개수인지 확인하는 것을 반복하여 랜선을 자를 수 있는 최대의 길이를 하도록 하였습니다.

 

랜선을 자를 수 있는 범위는 가장 긴 랜선에 따라 달라지기 때문에 최대값으로 설정하였습니다.

예제입력에서는 길이가 가장 긴 802가 최대값이 되어서 1~802 범위에서 이분탐색을 진행할 것입니다.

 

그래서 1~802 범위에서 이분탐색으로 중간값을 얻어서 랜선들을 중간값으로 잘랐을 때 필요한 랜선의 수가 나오는지 확인하는 것을 반복하여 최대 자를 수 있는 길이를 얻어내는 것입니다.

 

예제입력으로 진행되는 과정을 살펴보겠습니다.

랜선을 자를 수 있는 최대 길이 = 802, 최소 길이 = 1

1

~

802

1. 중간값은 (1+802)/2 = 401입니다.

랜선들을 401로 나누어보겠습니다.

802	/401	= 2
743	/401	= 1
457	/401	= 1
539	/401	= 1

얻어낸 랜선의 개수는 5개로 필요한 랜선에 개수 11개보다 적어서 더 작은 길이로 랜선을 잘라야 합니다.

 

그래서 자를 수 있는 더 작은 길이는 최대길이 = 400, 최소길이 = 1

1

~

400

2. 중간값은 (1+400)/2 = 200입니다.

랜선들을 200으로 나누어보겠습니다.

802	/200	= 4
743	/200	= 3
457	/200	= 2
539	/200	= 2

얻어낸 랜선의 개수는 11개로 필요한 랜선의 개수와 같습니다.

 

여기서 결과를 도출하는 것이 아닌 문제에서는 11개가 되면서 자를 수 있는 최대의 길이를 구해야하기 때문에 이제부터는 최대로 자를 수 있는 랜선의 길이를 구하는 것입니다.

200보다 자를 수 있는 더 큰 길이는 최대길이 = 400, 최소길이 = 201

201

~

400

3. 중간값은 (201 + 400) / 2 = 300입니다.

랜선들을 300으로 나누어보겠습니다.

802	/300	= 2
743	/300	= 2
457	/300	= 1
539	/300	= 1

얻어낸 랜선의 개수는 6개이므로 필요한 랜선보다 적으므로 더 작은 길이로 랜선을 잘라야 합니다.

 

그래서 자를 수 있는 작은 길이는 최대길이 = 299, 최소길이=201

201

~

299

위 과정을 반복하여 최소길이가 최대길이보다 커질 때 최대길이가 필요한 랜선의 개수를 구할 수 있는 최대로 자를 수 있는 값이 됩니다.

위 과정을 반복하고 마지막에는 범위는(최대길이 = 200, 최소길이 = 201)

201

~

200

결과적으로 최대길이 값 200이 출력됩니다.

 

문제를 해결한 알고리즘의 과정입니다.

1. 랜선의 최대길이를 구해서 자를 수 있는 최대값을 구하였습니다.

2. 범위(1 ~ 최대길이)에서 중간값을 구합니다.

3. 중간값을 통해 랜선들을 잘라서 필요한 개수가 나오는지 확인합니다.

4. 필요한 개수가 나오면 중간값보다 더 큰 범위로, 나오지 않는다면 작은 범위로 이분탐색을 진행합니다.

5. 위 과정을 반복하여 최소길이가 최대길이보다 커졌을 때 최대길이를 반환합니다.

 

※중간값 구하는 공식 = (시작값 + 최대값) / 2

• BufferedReader를 사용하여 입력 값을 받았습니다.
• StringTokenizer를 이용하여 N과 K을 나누었습니다.
• 자를 수있는 최대길이/자를 때 나오는 랜선 개수를 구하는 lineLength,quotientSum함수를 만들었습니다.
• 함수를 실행 후 BufferedWriter에 자를 수 있는 최대길이를 저장하였습니다.
• BufferedWriter에 저장된 결과값을 출력하였습니다.

• lineLength함수에서 이분탐색을 사용하여 중간값을 반복적으로 얻어 랜선을 잘라보았습니다.
• quotientSum함수에서 중간값만큼 길이를 잘라서 얻는 랜선의 개수를 구하였습니다.

 

결과 코드

import java.io.*;
import java.util.*;
public class Main{
	static int[] line;	//랜선 길이 저장 배열
    public static void main(String[] args) throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        //입력값 처리하는 BufferedReader
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        //결과값 출력하는 BufferedWriter
        //----------입력값 저장 및 최대 길이 구하기--------
        StringTokenizer st = new StringTokenizer(br.readLine(), " ");
        int K = Integer.parseInt(st.nextToken());
        int N = Integer.parseInt(st.nextToken());
        int max = Integer.MIN_VALUE;
        line = new int[K];
        for(int i=0;i<K;i++) {
        	line[i] = Integer.parseInt(br.readLine());
        	max = Math.max(max, line[i]);
        }
        bw.write(lineLength(N, K, max) + "\n");	//함수 결과 BufferedWrtier 저장
        bw.flush();		//결과 출력
        bw.close();
        br.close();
    }
    //---------랜선 자를 수 있는 최대값 구하는 함수--------
    public static long lineLength(int N, int K, int max) {
        long start = 1;		//최소 길이
        long end = max;		//최대 길이
        while(start<=end) {
        	long median = (start + end)/2;	//중간값
        	int temp = quotientSum(K, median);	//중간값으로 잘랐을 때 개수
        	if(temp<N)	//필요한 개수보다 작았을 때
        		end = median - 1;
        	else	//필요한 개수보다 컷을 때
        		start = median + 1;
        }
        return end;
    }
    //----------중간값으로 랜선 자를 때 나오는 개수--------
    public static int quotientSum(int K, long median) {
    	int temp = 0;
    	for(int i=0;i<K;i++)
    		temp += line[i]/median;
    	
    	return temp;
    }
}