Red Salmon

출처 : https://www.acmicpc.net/problem/2805

정답 :  https://github.com/stemp12/study/blob/master/acmicpc.net/2016.07/2805.cpp

이 문제는 이진탐색 문제이다. 문제를 딱보니 DP아니면 이진탐색의 느낌이 강했고, 더 살펴보니 이진탐색 문제였다.

DP 문제가 아니라는건 뭔가 감이었다. 예전에는 이런 구분이 잘 안되었는데 이젠 그냥 뭔가 보인다.

 문제는 어떤 기점으로 잘랐을때 요구한 길이에 가장 근접하게 자르라는 말이다.  예전에 황소 울타리문제? 그거랑 비슷한거 같다.

접근은 다음과 같다.

1. 정렬한다.

2. 먼저 입력값을 통해 대강적인 위치를 찾는다. (지금 생각해보니 굳이 찾을 필요가 없다.) 대강적인 위치는 입력배열의 인덱스이다.

3. 해당 인덱스를 통해 left right값을 구하면 이제 값은 arr[left]<=정답<=arr[right] 인것이기 때문에 범위가 상당히 좁아졌다. 여기서부터는 인덱스가 아닌 값으로써 다시 검색을 한다.

4. 일치되는 값이 있으면 그 값을 리턴하고 없다면 middle을 가지고 다시 state함수를 호출하여 middle을 그대로 사용할지 아니면 -1을 해줘야할지 판별한다. 

이 문제를 풀면서 조금 졸렸고, 코드가 길어져 짜증나 계속 줄이려고했는데 생각해보니 몇몇의 개선점이 보인다.

1. state함수는 계속 합을 구하는 함수인데, 좀 더 생각해보면 처음 이진탐색이후 3번과정을 할때는 이미 arr[right]로 값이 변경된 시점에서 right는 고정이 되었으므로 한번에 합을 구하고 그 후부터는 인덱스가 변할때 그 차만큼 +1 혹은 -1을 해주면 되지 않았을까 싶다. 그러면 굳이 처음부터 끝까지 합을 구하는 과정이 많이 생략되었을거 같다. 뭐 어차피 로그시간대라서 그냥 무시하고 진행하였다...

2. 나는 이진탐색을 둘로 나누었는데 지금 생각하니 굳이 그럴 필요가 없는것 같다. 하나만두고 처음부터 값을 통해 찾았다면 더 나은 코드가 되지 않았을까 생각이 든다. 역시 졸릴땐 문제를 풀면 안되는것 같다. 코드가 더 간략해지고 깔끔해질수있었을텐데 하는 아쉬움이 남는다.