백준 (2512) - 예산

 

이번 문제는 새롭게, 이진 탐색과 매개변수 탐색을 활용하는 문제이다

 

이진 탐색은 정렬된 배열에 대해 start, mid, end 값을 변경해가며 값을 찾는 과정이다

 

초기 값은 다음과 같다

start = 0;

end = n - 1;

mid = parseInt(start+end)/2))

 

하지만 우리는 배열에서 존재하는 값에서 mid 값이 아닌, 새로운 mid 값을 찾아야 하기 때문에 

상한액의 가장 작은 값은 0, 가장 큰 값은 배열의 맨 마지막 값이기에 

이 둘을 가지고 중간 값을 정한다

값은 (0 + 150) / 2 = 75로,

해당 배열 인덱스 값을 모두 순회하며 75보다 작으면 그 값을 사용하고, 크다면 75를 사용한다

let start = 0;
let end = arr[n-1];
let mid = parseInt((start + end)/2);

let mid = parseInt((start + end)/2);

for(let i =0; i< n; i++)
{
    total += Math.min(arr[i], mid);
}

 

110, 120, 140, 150 배열에 값에 대입해보면

75, 75, 75, 75로 300이다 

우리의 목표값인 485 >= 300 이므로, 중간 값을 75 + 1한 값으로 start를 76으로 설정하여 다시 mid 값을 계산한다

(76 + 150) / 2 = 113으로,

110, 113, 113, 113으로 449이다

우리의 목표값인 485 >= 449으로, 중간 값을 113 + 1한 값으로 start를 114으로 설정하여 다시 mid 값을 계산한다

(114 + 150) / 2 = 132

110, 120, 132, 132으로 494이다

우리의 목표값인 485 <= 494으로, 중간 값을 end 값을 -1한 값으로 131로 섲렁하여 다시 mid 값을 계산한다.

 

위에서 t보다 큰 경우와 작은 경우를 모두 살펴보았다.

이러한 반복을 통해 모든 경우의 수를 이진탐색으로 확인하는 아래 조건이 만족되면 종료되어 

start <= end

 

 

최종 mid 값을 출력하면 된다.