코딩테스트 문제 (22) - 랜선 자르기

문제

1. Ks = [802, 743, 457, 539], N = 11 
=> 200

 

풀이

K개의 랜선의 길이가 주어졌을 때, N개의 랜선을 만들 수 있는 가장 큰 랜선 자르는 길이를 구하는 문제입니다. 간단히 생각해보면 랜선을 자르기 위한 최대 길이는 배열 중 가장 긴 랜선이고 최소 길이는 1입니다. 즉, 1과 가장 긴 랜선 사이에 N을 만족하는 최대값을 구하면 되는 문제입니다.

이렇게 넓은 범위에서 특정 값을 찾는 문제는 이진 탐색 방법으로 풀 수 있습니다. Left, right를 양 끝으로 정하고 가운데를 탐색해서 그 가운데 값으로 랜선을 잘랐을 때 N보다 작으면 더 작은 값이 필요하니 right를 가운데로 옮기고 반대의 경우는 left를 가운데로 옮깁니다. Left를 가운데로 옮길 때 최대값을 계속 갱신합니다.

kaggle.com의 notebook으로 작성한 풀이는 다음과 같습니다.

 

홍머스 정리

• 난이도: 중
• 긴 범위 탐색 시는 이진 탐색으로

참조

• www.acmicpc.net/problem/1654