[백준] 코딩테스트 문제 풀이 : 1654.랜선 자르기 #이분탐색#매개변수탐색#BinarySearch
[문제]
이미 오영식은 자체적으로 K개의 랜선을 가지고 있다. 그러나 K개의 랜선은 길이가 제각각이다. 박성원은 랜선을 모두 N개의 같은 길이의 랜선으로 만들고 싶었기 때문에 K개의 랜선을 잘라서 만들어야 한다.
예를 들어 300cm 짜리 랜선에서 140cm 짜리 랜선을 두 개 잘라내면 20cm는 버려야 한다. (이미 자른 랜선은 붙일 수 없다.)
편의를 위해 랜선을 자르거나 만들 때 손실되는 길이는 없다고 가정하며, 기존의 K개의 랜선으로 N개의 랜선을 만들 수 없는 경우는 없다고 가정하자.
그리고 자를 때는 항상 센티미터 단위로 정수길이만큼 자른다고 가정하자. N개보다 많이 만드는 것도 N개를 만드는 것에 포함된다.
이때 만들 수 있는 최대 랜선의 길이를 구하는 프로그램을 작성하시오.
[접근 방법]
문제를 읽고 바로 떠올린 생각은, 현재 가지고 있는 k개의 랜선을 길이를 기준으로 오름차순 정렬한 뒤 가장 긴 랜선을 꺼내 절반으로 자르고,
이진 탐색으로 잘려진 2개의 같은 길이 랜선을 다시 배열에 넣어 우선 순위 큐를 구현해서 해결하려고 했다.
그러나 단순히 절반으로 잘라서 우선순위 큐를 구현할 경우, 743을 200,200,200이 아닌, 185,185,371로 나눠버리기 때문에 최소값이 최대가 되게 하기 위해서는
이 방법은 적절하지 않았다.
그래서 문제의 분류를 확인하니 ‘매개변수 탐색’이라는 알고리즘 적혀 있어 이 알고리즘이 무엇인지 알아보았다.
매개 변수 탐색
여러 개의 블로그를 읽어보니 각자 자신이 이해한 대로 매개 변수 탐색에 대한 정의를 내리고 있는데, 내가 이해한 바를 적어보자면,
특정 값을 계산하는 것이 아니라 “임의의 값이 주어진 조건을 만족하는지 확인하여 해당 조건을 만족하는 최대값(또는 최소값)을 찾는 것”이라고 할 수 있겠다.
즉, 이진 탐색의 원리를 응용하자면 이진 탐색은 기본적으로 전체 배열에서 배열의 양 끝을 기준으로 절반씩 나눠 원하는 값이 그 절반 안에 있는지 없는지를 판단하여 원하는 값이 있을 범위를 점점 좁혀나가는 탐색 방법이다.
마찬가지로 매개 변수 탐색 역시, 가장 먼저 두 포인트를 잡는다. 한 포인트는 주어진 조건을 무조건 만족하는 값이다. 이 문제에서는 N개의 랜선을 만드는 가장 작은 랜선 길이 즉, 0이 된다.(1로 잡아도 상관 없다.)
나머지 한 포인트는 주어진 조건을 무조건 만족하지 않는 값이다. 예제에서는 주어진 랜선의 길이 중 가장 긴 길이인 802보다 1이 더 큰 803이 다른 한 포인트 값이 될 것이다.
길이가 803인 랜선의 길이는 주어진 랜선을 가지고는 절대 만들 수 없는 길이다.
이렇게 양 끝 점을 설정한 뒤에는 우리가 알고 있는 이진 탐색의 알고리즘과 동일하다. 양 끝의 절반을 기준으로 가운데에 있는 길이를 만든다고 가정했을 때 주어진 랜선들로 해당 길이의 랜선을 N개 이상 만들 수 있는지 없는지 확인하는 함수를 만들어 체크해주고 만들 수 있다면 만족하는 값을 mid 값으로 바꿔주고 만들 수 없다면 만족하지 않는 값을 mid로 바꿔주고 탐색을 지속하다가 start(주어진 조건을 무조건 만족하는 값을 저장한 변수)이 end(주어진 조건을 무조건 만족하지 않는 값을 저장한 변수)와 같거나 커지면 반복문을 빠져나와 start를 return한다. (이진 탐색의 정의 : arr[x] <= x <arr[x+1]인 x가 가질 수 있는 가장 큰 인덱스)
이렇게 풀 경우 정답을 찾을 수 있다.