[JAVA-1654] 랜선 자르기(결정 알고리즘)

1654번: 랜선 자르기

링크를 클릭하면 해당 문제로 이동합니다.

 

출처 - 백준

---

해당 문제에 대한 시각은 내가 결정 알고리즘이라는 것을 알기 전과 후로 나뉜다.

내 기준에서는 나름 어려웠던 문제인데 구글링하지 않고 혼자 풀어낸 것에 대한

성취감이 느껴져서 어떻게 풀었는지 잊지 않기 위해 기록해본다.

 

결정 알고리즘이란?

 

결정 알고리즘이라는 단어는 실제 공식적으로 사용 되어지는 단어는 아니고,

내가 개인적으로 인프런에서 수강중인 강의의 강사님께서 만든 단어인거 같다.

 

어쨌든, 결론은 이분 탐색(Binary Search)을 이용하여 문제를 해결하는 것인데

간단히 말해 임의의 숫자 a(보통은 최솟값)와 숫자 b(보통은 최댓값)를 지정해놓고

숫자 a와 숫자 b 사이에 문제에서 요구하는 답이 존재하는게 확실하다면

그 때 결정 알고리즘을 이용한다고 한다.

 

여기서 의문이 들 수 있는 부분은 그렇다면 왜 해당 문제를 결정 알고리즘으로 풀었냐인데

 

 

바로 하이라이트 된 부분 때문이다.

 

문제에서 주어진 필요한 랜선의 개수 N은 가지고 있던 랜선들을 1cm 단위로 잘라도 답이 될 수 있기 때문이다.

(길이 802cm 랜선을 1cm 단위로 자르면 802개, 길이 743cm 랜선을 1cm 단위로 자르면 743개...

총 2541개의 랜선을 얻을 수 있다. 문제에서 주어진 N값인 11보다 많으니까 정답이 된다.)

 

그래서 보통은 최솟값으로 한다고 했던 임의의 숫자 a는 1이 되겠고

임의의 숫자 b가 될 최댓값은 길이가 제일 긴 랜선인 802가 되겠다.

 

접근하기

 

결정 알고리즘에 대한 개념이 어느정도 정립되었으면, 이분 탐색으로 문제를 풀어나가면 되겠다.

 

TO-DO

1. 임의의 숫자 a(최소값), 임의의 숫자 b(최댓값)을 담을 변수 2개를 생성한다.

2. 이분 탐색을 해야 하므로, 변수 mid에 a와 b의 중간값을 담는다.

3. 가지고 있는 랜선들을 중간값으로 잘랐을 때, 필요한 랜선의 개수보다 적게 얻게 되면 최댓값을 중간값 - 1로 변경

3-1. 혹은, 같거나 많이 얻게 되면 중간값을 answer에 저장 후에, 최솟값을 중간값 + 1로 변경

4. a가 b보다 작거나 같을 때까지 위 과정을 반복

 

코드

 

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.Arrays;
import java.util.StringTokenizer;

public class Main {

	public static void main(String[] args) throws Exception {
		// 랜선 자르기(결정 알고리즘)
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
		StringTokenizer st = new StringTokenizer(br.readLine());
		
		// 가지고 있는 랜선의 개수
		int K = Integer.parseInt(st.nextToken());
		// 필요한 랜선의 개수
		int N = Integer.parseInt(st.nextToken());
		
		long[] arr = new long[K];
		for(int i = 0; i < K; i++) {
			arr[i] = Long.parseLong(br.readLine());
		}
		
		// 최소값
		long lt = 1;
		// 최대값
		long rt = Arrays.stream(arr).max().getAsLong();
		long answer = 0;
		while(lt <= rt) {
			long mid = (lt+rt) / 2;
			if(count(arr, mid) >= N) {
				answer = mid;
				lt = mid + 1;
			} else {
				rt = mid - 1;
			}
		}
		
		bw.write(String.valueOf(answer));
		bw.flush();
		bw.close();
	}
	
	// 특정 길이로 잘랐을 때, 얻을 수 있는 랜선의 개수 구하는 메소드
	static long count(long[] arr, long length) {
		long sum = 0;
		for(long i : arr) {
			sum += i / length;
		}
		return sum;
	}
}

 

리뷰

 

확실히 쉬운 문제보다 어려운 문제를 풀 때 더 머리를 싸매게 되긴 하는데 풀었을 때의 성취감은 더 크다.

Arrays 클래스의 stream메소드를 이용해 최솟값, 최댓값, 합계를 구하는 법도 배웠다.

다음주에 다시 또 풀어보자.