[JAVA] BOJ_1654. 랜선 자르기

🐒 문제

1654번: 랜선 자르기

 

---

🐈 문제풀이 핵심

이분 탐색 기법을 사용할 줄 알고, 어떤 상황에서 어느쪽 절반을 택해 탐색을 파고 들어가야할 지 결정할 수 있어야 하는 문제였다. 한 쪽 절반을 선택하여 파고 들어가는 부분을 결정하는데 특정 변수의 값을 기준으로 하기 때문에 이분 탐색의 응용인 매개 변수 탐색(Parametric search)을 진행하여야 한다.

 

아래 예시를 보자.

길이가 9인 랜선 1개를 가지고 있고, 이를 잘라 길이가 균등하면서 가장 긴 랜선 3개를 만들고자 한다.

start = 1, end = 9 에서부터 메서드가 시작된다.

length 값은 start와 end의 중간값을 가지게끔 한다. --> length = (start+end)/2;

 

1) 

start = 1 // end = 9 // length = 5 // cnt = 1

첫 단계에서 자른 랜선의 길이는 5로, 이것으로는 균등한 길이의 랜선을 1개 밖에 만들지 못한다.

따라서 랜선의 길이를 줄이는 방향으로 진행해야 한다 -- > start = 1 // end = length - 1

---

2)

start = 1 // end = 4 // length = 2 // cnt = 4

두번째 단계에서는 길이 2짜리로 4개의 랜선을 만들 수 있었다.

이는 만들고자 하는 3개의 랜선보다 하나가 더 많으니, 랜선의 길이를 늘리는 방향으로 진행해야 한다

--> start = length +1 // end = 4

---

 3)

start = 3 // end = 4 // length = 3 // cnt = 3

세번째 단계에서 길이 3짜리 랜선을 3개 만들수 있게 되었다.

만들어진 랜선의 개수가 요구하는 랜선의 개수와 일치한다.

해당 문제는 랜선의 개수를 필요한 만큼 만들되, 길이를 최대한으로 길게 해보라고 했으므로 길이를 조금 더 늘려보는 방향으로 진행해보자. --> start = length + 1 // end = 4

---

 

4)

start = 4 // end = 4 // length = 4 // cnt = 2

네번째 단계에서 길이가 4로 늘어나며 개수가 2개로 줄어들었다.

개수를 다시 3개로 맞춰주기 위해 길이를 다시 줄여주는 방향으로 진행해야 한다. --> start = 4 // end = length -1

---

5)

 start = 4 // end = 3 // length = 3 // cnt = 3

다섯번째 단계에서 길이가 3짜리 랜선 3개를 만들 수 있게 되었다.

또한 start가 end보다 커졌으므로 더 이상 탐색을 진행할 방향이 존재하지 않게되어 해당 길이를 저장하고 메서드를 종료한다.

 

위 과정을 거쳐 정답인 3을 출력할 수 있게 된다.

---

🦍 풀이 전략

1. 랜선의 길이를 최대로 하며 N개의 랜선을 만들어야 하되, 자른 랜선의 길이는 모두 동일해야 한다.
 - 따라서 중간 길이의 랜선을 만들어보고, 해당 길이로 몇개의 랜선을 만들 수 있는지 파악하여 길이를 늘려야 할지, 줄여야 할지를 결정해야 한다. 이를 하나의 재귀 메서드로 구현하였다.
 - 이분탐색에서는 중간값과 찾고자 하는 키 값을 비교하면서 진행하였다면, 해당 문제에서는 중간값인 랜선의 길이를 통해 만들어진 랜선의 개수와 요구하는 랜선의 개수를 비교하였다.

 

2. 입력받는 자료의 자료형에 주의해야한다.

 - 입력받는 랜선의 최대 길이가 2^32 - 1 까지 들어올 수 있다. 이 때 매개 변수 탐색 메서드 내에서 length를 구하는 과정에서 int 범위를 초과해 올바르지 않은 계산이 이뤄질 수 있다.
 - 랜선 길이의 입력 자체는 int형으로 받아줘도 괜찮으나, 연산 과정에서 범위를 초과할 수 있으므로, parametricSearch 메서드에서는 long 으로 받아 이를 방지하였다.

---

🐕‍🦺 소스 코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class Main {
	static int K, N;
	static long ans;
	static int[] arr;

	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		StringBuilder sb = new StringBuilder();

		// K : 이미 가지고 있는 랜선의 개수
		K = Integer.parseInt(st.nextToken(" "));
        
		// N : 필요한 랜선의 개수
		N = Integer.parseInt(st.nextToken(" "));

		// arr : 가지고 있는 랜선의 길이를 저장할 배열
		arr = new int[K];

		// max : 가지고 있는 랜선의 최대 길이를 저장
		int max = 0;
		for (int i = 0; i < arr.length; ++i) {

			// 배열에 랜선 길이 정보 저장
			arr[i] = Integer.parseInt(br.readLine());

			// 가지고 있는 랜선의 최대 길이를 갱신
			if (max < arr[i]) {
				max = arr[i];
			}
		}

		// 매개 변수 탐색
		parametricSearch(1, max);

		System.out.println(ans);
	}

	static void parametricSearch(long start, long end) {
    
		// length : 새로 자른 랜선의 길이
		long length = (start + end) / 2;
        
		// 탐색이 모두 끝났을 때
		if (start > end) {

			// ans : 출력할 정답. 현재의 길이를 저장한다.
			ans = length;
			return;
		}

		// cnt : 새로 자른 랜선의 길이로 만들 수 있는 새 랜선의 개수
		int cnt = 0;
		for (int i = 0; i < arr.length; i++) {

			// 가지고 있는 랜선의 길이를 length로 나누어주며 개수를 센다.
			cnt += arr[i] / length;
		}

		// 새로 자른 랜선의 개수 < 필요한 랜선의 개수 --> 길이를 줄여 더 많은 랜선을 만들어야 한다.
		if (cnt < N) {

			// 길이를 짧게 하는 방향으로 탐색
			parametricSearch(start, length - 1);
		}
		// 새로 자른 랜선의 개수 >= 필요한 랜선의 개수 --> 길이를 늘려 더 적은 랜선을 만들어야 한다.
		// 개수가 같을 때는 최대한 그 길이를 늘려야 한다.
		else if (cnt >= N) {

			// 길이를 늘리는 방향으로 탐색
			parametricSearch(length + 1, end);
		}
	}
}

🐖 Think

 - 이분 탐색을 처음 공부했을 때는 어디에 적용시켜야 하는건지 생각하기 어려웠는데, 최근 재귀 문제를 많이 풀다보니 이분 탐색이 정말로 많이 쓰이고 중요하다는 점을 알게 되었다.

 - 단순 이분 탐색 뿐만 아니라 특정 변수를 중점으로 좌 우를 나눠가며 탐색하는 기법에 조금 더 익숙해져야겠다.