[백준, 1654번] 랜선 자르기 (이진 탐색, 이분 탐색, Java)

문제설명

입력 & 출력

나의 풀이

문제 접근 방법

"백준 - 랜선자르기" 문제는 길이가 서로 다른 K개의 랜선이 주어질 때, 이를 잘라서 동일한 길이의 랜선 N개를 만들 수 있는 최대 길이를 구하는 문제입니다.

4 11
802
743
457
539

 

입력이 위와 같이 주어질 때 정확히 11개의 랜선을 만들 수 있는 길이는 186cm에서 200cm까지 총 15가지가 있습니다. 이 중에서 문제에서 요구하는 것은 최대 길이인 200cm입니다.

• 180cm~185cm로 자르면 ➡️ 12개
• 200cm보다 큰 길이로 자르면 ➡️ 11개 미만

즉, 문제의 핵심은 동일한 길이의 랜선 N개를 만들 수 있는 최대의 길이를 찾는 것입니다.

 

여기서 알 수 있듯이 랜선을 자를 수 있는 길이가 연속적으로 여러 개 존재합니다. 이처럼 연속된 범위에서 조건을 만족하는 최대값을 찾아야 할 때 이진 탐색을 사용하면 효율적으로 풀이할 수 있습니다.

[Algorithm] 이진 탐색 알고리즘 : 데이터 정렬과 검색 최적화 (Binary Search, Java)

 

---

 

위와 같이 같은 길이를 가지는 랜선을 N개로 잘라야 하는 최대의 길이를 구해야하기 때문에 잘랐을 때 원하는 N개 보다 많이 나온다면 길이를 늘려 개수를 줄이고, 적게 나온다면 길이를 줄여 개수를 늘리는 방식으로 접근하면 됩니다.

 

• left를 늘리면 → mid 값이 커짐 → 자르는 길이가 길어짐 → 잘린 개수가 적어짐
• right를 줄이면 → mid 값이 작아짐 → 자르는 길이가 짧아짐 → 잘린 개수가 많아짐

 

---

 

 

예제 입력1번을 예로 그림으로 표현하면 위와 같이 길이를 조정하여 200으로 잘랐을 때의 결과입니다. 

 

전체 코드