[Binary Search]백준-2343

https://www.acmicpc.net/problem/2343

2343번: 기타 레슨

 

쉽게 생각할수 있는 이분탐색 풀이이다.

이분탐색의 유형은 크게 두가지 풀이이다.

특정 배열이 있고, 해당 배열 내에서, 이분탐색으로 중간값을 구해서 값을 탐색하는 방법이 있고

특정 조건에 대한 리스트들을 생각해서, 만든뒤에 해당 조건들의 범위에서 이분탐색을 하는 경우가 있다.

해당 문제는 두번째 케이스이다.

 

각 레슨의 길이를 생각해서 최대의 길이를 계산, 그리고 cnt 를 증가 시키면서 세는 방법이다.

 

우선 소스든 최 하단에 있다.

가장 중요하게 생각해야하는 포인트가 범위는 각 레슨의 합이 될수있는 값들이다.

1. 가장작은값은 -> 배열의 가장작은 혼자의 값 또는, 0

2. 가장 큰값은 -> 배열의 모든 합이다.

 

따라서 end 는 배열의 모든 합, 반복 -> end+=les[i] 이고

해당 값을 기준으로 체크하는 함수에 넣고, cnt를 세준다.

sum이 0부터, 하나씩 더해가면서 mid로 던진값보다 커지면 sum을 해당 값으로 초기화하고, cnt를 1증가해준다는게 포인트다