43강

43강

💎 접근법 :

• 43강 내용은 이분탐색을 이용한 결정알고리즘에 관한 내용이다. 결정 알고리즘이란 먼저 답을 정해놓고 그 정답이 맞는지를 확인하는 알고리즘이다.

• 문제에서 먼저 생각해야 할 점은 DVD에 들어갈 노래에 대한 리스트 값들을 모두 더한 값이 rt가 되고 1이 lt 그리고 mid에 값이 (rt+lt)/2 가 된다는 것이다.

• 이렇게 mid 값을 구했으면, 우리는 이 mid값이 최소가 되는 지점을 찾아야 한다. 그러기 위해서는 check 함수를 만들어야 한다.

• check함수는 mid값을 인수로 받아서 노래길이가 저장되어있는 전역변수에서 값을 가져와서 하나씩 더해서 값이 mid보다 크기 전까지 sum값을 구해서 거기까지를 한 묶음으로 생각하고 cnt의 값을 ++ 해준다.

• 마지막으로 check함수를 통해서 cnt 값을 return 해주고, 이 cnt 값이 입력받은 m이라는 값보다 작거나 같았을 때에 대해서, mid는 값을 만족하므로 현재 result 값과 비교를 하여 값이 더 작으면 result 값을 mid로 치환 해준다. 그리고 이 경우 이제 mid 값보다 큰 경우는 확인 할 필요가 없으므로 rt의 값을 mid-1로 해주고 다시 mid 값을 구해준다.

• 위 경우가 아니라 cnt값이 더 크다면 lt=mid+1로 해준다. 이 while문은 lt <= rt가 될때까지 반복한다.