문제 출처 : https://www.acmicpc.net/problem/1654
문제 정리
- 이미 오영식은 자체적으로 K개의 랜선을 가지고 있다. 그러나 K개의 랜선은 길이가 제각각이다. 박성원은 랜선을 모두 N개의 같은 길이의 랜선으로 만들고 싶었기 때문에 K개의 랜선을 잘라서 만들어야 한다.
- 예를 들어 300cm 짜리 랜선에서 140cm 짜리 랜선을 두 개 잘라내면 20cm는 버려야 한다. (이미 자른 랜선은 붙일 수 없다.)
- 편의를 위해 랜선을 자르거나 만들 때 손실되는 길이는 없다고 가정하며, 기존의 K개의 랜선으로 N개의 랜선을 만들 수 없는 경우는 없다고 가정하자. 그리고 자를 때는 항상 센티미터 단위로 정수길이만큼 자른다고 가정하자. N개보다 많이 만드는 것도 N개를 만드는 것에 포함된다.
- 이때 만들 수 있는 최대 랜선의 길이를 구하는 프로그램을 작성하시오.
문제 해결 방법
무작정 값을 찾으면 당연히 시간초과가 발생한다.
이 때 이진 탐색을 사용하면 된다.
→ 이진 탐색
여기서 응용을 해야하는데 기존의 이진 탐색은 배열의 인덱스를 가지고 찾았다면 이 문제에서는 길이를 가지고 찾아야한다.
입력 받은 랜선 중 가장 큰 값을 찾고 문제 조건이 항상 자연수이므로 min값은 1로 준다.
이 점을 확실하게 이해하면 평범한 이진 탐색과 크게 다르지 않다.
코드