[백준] 1654번 : 랜선 자르기 - JAVA [자바]

https://www.acmicpc.net/problem/1654

1654번: 랜선 자르기

 

 

 

 

 

 

 

 

 

---

• 문제

 

 

 

 

 

 

이분 탐색의 응용 문제다.

 

 

 

 

 

 

 

 

 

 

---

• 알고리즘 [접근 방법]

 

 

 

일단, 이 번 문제를 풀기 전에 이분 탐색 중 Upper Bound 에 대해 이해하고 있어야 한다.

그러니, 해당 원리를 이해하기 위해 아래 포스팅을 먼저 보시고 오시기를 바란다.

 

https://st-lab.tistory.com/267

[백준] 10816번 : 숫자 카드 2 - JAVA [자바]

 

 

 

풀이 자체는 그리 어렵지 않지만, 최대한 기존에 포스팅 했던 알고리즘(숫자 카드 2에서 썼던 방식)으로 풀이하려다가 어처구니 없는 곳에서 틀렸습니다를 좀 받았던 문제다..

 

 

 

 

일단, 이번 문제부터 이해해보자.

 

일단 기존의 K개의 랜선이 있고 똑같은 길이의 N개의 랜선으로 만들고자 할 때, N개의 랜선이 가질 수 있는 최대 길이를 알아내야 하는 것이다.

 

위 예제를 그림으로 보면 다음과 같다.

 

 

 

위와 같이 11개로 만들 수 있을 때 최대로 가질 수 있는 길이는 200이다.

 

만약 201 크기로 자른다고 한다면,

802 길이의 랜선은 201씩 3개로 603,

743 길이의 랜선은 201씩 3개로 603,

457 길이의 랜선은 201씩 2개로 402,

539 길이의 랜선은 201씩 2개로 402,

 

총 10개의 랜선을 갖게 되므로 11개를 만들 수가 없다.

 

반대로 200크기보다 작은 수로 한다면 11개 이상의 개수를 가질 수 있으나, 11개일 때의 최대 길이인 것은 아니다.

 

예로들어 198 크기로 자른다고 가정해보자.

802 길이의 랜선은 198씩 4개로 792, 

743 길이의 랜선은 198씩 3개로 594,

457 길이의 랜선은 198씩 2개로 396,

539 길이의 랜선은 198씩 2개로 396,

 

총 11개의 랜선을 갖게 되지만, 198 길이가 최댓값은 아니다.

 

 

그러면 문제는 200 크기 같이 최대로 가질 수 있는 길이를 어떻게 찾느냐인 것이다.

 

 

 

우리는 이분 탐색을 배웠다. 그동안은 배열에 대해 이분 탐색을 했지만, 이번에는 조금 관점을 바꿀 필요가 있다.

눈치 빠른 분들은 위 예시에서 감이 오실 수도 있다.

 

어떤 관점을 바꿔야 할까?

 

그동안 배열에서의 이분 탐색은 특정 값에 대한 배열의 특정 인덱스를 찾기 위함이었다. 하지만 이 번 문제에서는 어떤 것을 찾아야 하는건가? 우리가 찾아야 할 대상은 결국 '길이' 라는 것이다. 그럼 일단 이분 탐색의 범위는 인덱스가 아닌 랜선의 길이를 의미한다고 보면 되겠다.

 

그러면 배열의 이분탐색과 하나씩 비교하면서 바꿔보자.

배열에서 이분 탐색을 할 때, 중간값을 어떻게 찾았는가? 현재 이분 탐색 범위에서 가장 왼쪽 인덱스(Index)인 lo와 가장 오른쪽 인덱스(index)인 hi의 중앙 인덱스를 참조했다.

즉, mid = (lo + hi) / 2 였다.

 

자, 그럼 이 문제에서 이분 탐색의 범위는 랜선의 길이라고 했으니 이를 그대로 적용해보자.

길이에 대해 중간값을 구하고자 한다면, 현재 탐색 범위(길이)의 최소 길이와 최대 길이가 있을 것이다. 이를 min과 max라고 한다면, 어떻게 해야겠는가?

똑같은 원리다. mid = (max + min) / 2 를 하면 중간 길이가 구해진다.

 

 

그 다음으로 가장 중요한 어떤 것을 기준으로 범위를 좁힐 것인가다. 배열의 경우 특정 값인 key값과, 각 순회 단계에서 구해진 mid 값을 통한 arr[mid] 의 비교를 통해 lo 혹은 hi를 좁혀나갔다.

그렇다면, 이 번 문제에서의 key 값은 무엇인가? 바로 입력으로 들어오는 N, 즉, 만들고자 하는 랜선 개수를 의미한 다는 것을 알 수 있다.

즉, 배열에서는 원소 값의 비교였다면 랜선 자르기에서는 개수 비교인 것이다.

 

 

정리해보자면 이렇다.

배열에서는 특정 값에 대한 특정 인덱스를 찾고자 했다면, 이 번 문제에서는 특정 개수에 대한 특정 길이를 찾고자 한다는 것이다.

 

 

 

왜 이렇게까지 길게 설명하는가..? 라고 할 수 있지만, 위 메커니즘을 이해해야 하는 부분이 있다.

필자가 숫자 카드 2 문제 포스팅을 보고오라고 한 이유가 바로 여기에서 나타나는데, 해당 글을 보고 오셨다면 알겠지만, 이분 탐색에서는 크게 두 가지 방식이 존재한다.

 

바로 Upper Bound(상한)와 Lower Bound(하한)이다.

상한은 찾고자 하는 특정 값을 초과하는 '첫 위치'를 반환한다.

하한은 찾고자 하는 특정 값 이상인 '첫 위치'를 반환한다.

 

이 것에 대해 중요한 점은 중복 값이 있을 때의 활용 때문이다.

 

예로들어 arr{1, 2, 2, 2, 3} 이라고 할 때, key 값은 2이고, Upper Bound로 찾는다면 2를 초과되는 처음 위치인 arr[4] = 3 인 index 4가 반환 될 것이다.

 

반대로, Lower Bound로 찾게 된다면 2 이상 위치 중 처음 위치인 arr[1] = 2 인 index 1이 반환 될 것이다.

 

만약 중복 원소에서 가장 끝 값(가장 오른쪽 값)을 찾고자 한다면 Upper Bound - 1 을 하면 될 것이고, 중복 원소 중 가장 왼쪽 끝 값(가장 왼쪽 값)을 찾고자 한다면 Lower Bound 을 통해 반환 된 값 그대로가 된다.

 

그럼 이 번 문제에서는 어떤 방식을 채택해야 할까?

필자가 예시로 든 케이스에서 찾을 수 있듯 key값, 즉 개수가 중복이 될 떄 최대 길이를 찾아야 한다는 것이다. 쉽게 말해 Upper Bound를 통해 얻어진 값에서 -1을 해주면 최대 길이가 된다. 

 

즉, Upper Bound 방식을 활용해야 한다.

 

앞서 보았던 예시에서도 볼 수 있다.

198cm 로 자를 때의 개수는 11개다. 그리고 199cm, 200cm 로 자를 때 또한 모두 11개다. 이렇게 자른 개수가 중복이 되지만, 최대 길이를 찾기 위해서는 Upper Bound를 써야한다는 것이다.

Upper Bound를 쓰면 201 이 반환 될 것이고, 여기서 이 반환 된 값은 특정 개수(N)을 초과한 첫 길이(=12개로 자를 때 만들 수 있는 최소 길이)이기 때문에 -1을 해주면 11개로 만들 수 있는 최대 길이가 되는 것이다.

 

 

위 내용들을 토대로 알고리즘을 짜보자.

 

// min = 0, max 는 입력받은 LAN선 중 가장 긴 길이를 갖는다.
while (min < max) {

// 범위 내에서 중간 길이를 구한다.
mid = (max + min) / 2;

long count = 0;

// 구해진 중간 길이로 잘라서 총 몇 개가 만들어지는지를 구한다.
for (int i = 0; j < arr.length; i++) {
count += (arr[i] / mid);
}

/*
* [upper bound 형식]
*
* mid길이로 잘랐을 때의 개수가 만들고자 하는 랜선의 개수보다 작다면
* 자르고자 하는 길이를 줄이기 위해 최대 길이를 줄인다.
* 그 외에는 자르고자 하는 길이를 늘려야 하므로 최소 길이를 늘린다.
*/
if(count < N) {
max = mid;
}
else {
min = mid + 1;
}

}

 

위와 같이 작성을 해주면 된다.

 

 

기존 배열에서의 이분 탐색과 다른 점이라면, 특정 Key값에 대해 arr[mid]와 비교했던 것과는 달리 우리는 만들고자 하는 개수가 key이고, 잘라진 mid 길이로 잘랐을 때 잘린 개수와 비교해야 하므로 각 순회 단계에서 for문을 통해 랜선을 잘라서 개수를 구해야 한다.

 

그에 대한 변수가 바로 count다.

 

그리고 우리는 길이를 구하기 때문에 배열의 원소값과 그에 대한 특정 인덱스를 찾는 것이 아니라서 굳이 배열을 절렬해줄 필요도 없다.

 

 

 

 

그리고 가장 중요한 점이 있다.

 

mid가 0이게 되면 그 다음 for문 안에  count += (arr[i] / mid) 부분에서 mid 가 0이라 0으로 나눗셈되는 불상사가 일어나게 된다.

 

생각해보자.

만약 2개의 랜선을 갖고 있고 2개의 랜선 모두 길이가 1이라고 해보자. 즉 {1, 1} 인 것이다.

이 때, min은 초기값으로 0을 갖고, max는 1이 된다.

 

그리고 이분 탐색을 통해 mid = (max + min) / 2 를 하게 되면 mid = (0 + 1) / 2가 되므로 mid = 0이 된다.

 

 

아마 많은 분들이 이러한 부분에서 런타임에러, 혹은 틀렸습니다를 많이 받으셨을 것이다.

해결 할 방법이 있을까?

 

간단하다. 우리는 최종적으로 상한을 통한 (Upper Bound - 1) 의 값을 쓰는 것이다. 이 의미는 Upper Bound는 자연수 범위에서는 특정 길이보다 1 크다는 의미이기도 하다.

 

아주 간단하게, 0 값만 존재한다 했을 때, min = 0, max = 0 이면 min < max 조건이 아니기에 이분탐색을 수행하지 않게 된다.

그렇게 되면 Upper Bound 값은 0이 되어버린다.

하지만, 실제로 Upper Bound로 반환 되어야 하는 값은 1이다.

 

그렇다면 해결 방법은 매우 간단하다. 자연수 탐색 범위를 0 ~ max 가 아닌 0 ~ max + 1 범위에서 탐색하면 된다.

즉, 우리는 입력 받는 랜선에서 최대 길이 + 1 을 max값으로 잡아야 한다는 것이다.

 

이 것만 조심한다면 문제를 어렵지 않게 풀 수 있다.

 

(참고로 주어지는 입력 범위는 int형의 최댓값까지 주어지기 때문에 모두 이분 탐색에 필요한 모든 변수들은 long 타입으로 잡아주도록 하자.)

 

 

 

 

 

 

---

• 풀이

- 방법 : [BufferedReader]

 

 

 

입력 방법을 BufferedReader 을 사용하여 풀이하는 방법이다. 단, BufferedReader 는 문자열을 한 줄로 읽기 때문에 K와 N을 구분하기 위해 공백을 기준으로 문자열을 분리해주어야하니 StringTokenizer 을 사용하여 풀도록 하겠다.

 

 

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

public class Main {

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

StringTokenizer st = new StringTokenizer(br.readLine(), " ");

int K = Integer.parseInt(st.nextToken());
int N = Integer.parseInt(st.nextToken());

int[] arr = new int[K];

long max = 0;

// 입력과 동시에 해당 랜선의 길이가 최댓값인지를 확인하고 max를 갱신
for (int i = 0; i < K; i++) {
arr[i] = Integer.parseInt(br.readLine());
if(max < arr[i]) {
max = arr[i];
}
}


// 반드시 max에서 +1 값이어야 한다.
max++;

long min = 0;
long mid = 0;

while (min < max) {

// 범위 내에서 중간 길이를 구한다.
mid = (max + min) / 2;


long count = 0;

// 구해진 중간 길이로 잘라서 총 몇 개가 만들어지는지를 구한다.

for (int i = 0; i < arr.length; i++) {
count += (arr[i] / mid);
}

/*
* [upper bound 형식]
*
* mid길이로 잘랐을 때의 개수가 만들고자 하는 랜선의 개수보다 작다면
* 자르고자 하는 길이를 줄이기 위해 최대 길이를 줄인다.
* 그 외에는 자르고자 하는 길이를 늘려야 하므로 최소 길이를 늘린다.
*/
if(count < N) {
max = mid;
}
else {
min = mid + 1;
}


}

// UpperBound로 얻어진 값(min)에 -1이 최대 길이가 된다.
System.out.println(min - 1);
}
}

 

 

 

본 글은 https://st-lab.tistory.com/269에서 발췌하였습니다.