#include <bits/stdc++.h>
using namespace std;

typedef pair<int, int> pii;
#define Strike first
#define Ball second

pii Check(string t, string ask)
{
	int cnt_s = 0;
	int cnt_b = 0;

	for (int i = 0; i < 3; ++i)
	{
		for (int j = 0; j < 3; ++j)
		{
			if (t[i] == ask[j])
			{
				if (i == j) ++cnt_s;
				if (i != j) ++cnt_b;
				break;
			}
		}
	}
	return { cnt_s, cnt_b };
}

string ask[101];
pii sb[101];

int main()
{
	ios::sync_with_stdio(0), cin.tie(0);
	int answer = 0;
	int n; cin >> n;

	for (int i = 0; i < n; ++i)
	{
		cin >> ask[i] >> sb[i].Strike >> sb[i].Ball;
	}

	string temp;
	pii tsb;
	int i, j;
	for (i = 123; i < 988; ++i)
	{
		temp = to_string(i);
		if (temp[0] == temp[1] || temp[0] == temp[2] || temp[1] == temp[2]) continue;
		if (temp[0] == '0' || temp[1] == '0' || temp[2] == '0') continue;

		for (j = 0; j < n; ++j)
		{
			tsb = Check(temp, ask[j]);
			if (sb[j] != tsb) break;
		}
		if (j == n) ++answer;
	}
	cout << answer;
	return 0;
}

||사고 과정

이건 경우의수를 어떻게 for문으로 돌리는지 몰라서 이 부분만 다른 사람의 아이디어를 가져왔다.

내가 너무 어렵게 생각했었다.

123 ~ 987 까지의 순서도 상관없는 모든 경우의수를 어떻게 찾지? 하고 낑낑대며 고민했는데

그냥 123 부터 987까지 1씩 증가하면 되는거였다.....😑

정말 이거 알고 머리가 띵했다.... 바보인듯ㅜ

이 수를 어떻게 돌릴지 알고나서는 수월했다.

각 숫자가 모든 질문에 해당이 되면 카운트를 올린다.

즉 123 ~ 987 까지인 대략 900개와 최대 질문 개수인 100개,

이를 곱한 900 * 100 = 90'000 연산은 1초안에 충분했다.

심지어 가지치기로 122, 131, 424 처럼 중복이 들어간 수는 제외하고

특히 내가 마지막에 못찾았던 0이라는 예외도 처리해주면 더 줄어들것이다.

||사용 기법

• Brute Force

||풀면서 느낀 것

• continue, break

이거 두개를 자꾸 헷갈리게 사용해서 시간을 소모한적이 최근에 많고 이 문제에서도 그랬다.

주의할것

• 문자 비교

바보처럼 자꾸 정수랑 비교한다. 확실히 할것.

char c = '3';

//정수랑 비교 - X		//문자랑 비교 - o
if(c == 3)				if(c == '3')

||새로 알게 된것

• 123 ~ 987

이건 진짜 잘 배운것같다.

지금 아니였으면 또 어딘가에서 헤맸을것.

이 문제처럼 고정 자리인 부분집합에 완전 탐색이면 자주 사용할것 같다.

||다른 풀이

//1.
for(int i = 0; i < n; ++i)
{
	for(int j = 0; j < n; ++j)
	{
		for(int k = 0; k < n; ++k)
		{
			//i가 백의자리숫자, j가 십의자리숫자, k가 일의자리숫자
		}
	}
}


//2.
for(int i = 123; i < 987; ++i)
{
	int a = i / 100;
    int b = i % 100 / 10;
    int c = i % 10;
}

나는 문자로 변환해서 비교했지만

많은 사람들이 이렇게 정수로 비교하곤했다.

#include <bits/stdc++.h>
using namespace std;
#define DP(x) if(dp[x] == 0) dp[x] = x * (x + 1) / 2

int dp[50];

int main()
{
	ios::sync_with_stdio(0), cin.tie(0);
	int t; cin >> t;

	while (t--)
	{
		int n; cin >> n;

		bool pass = false;
		int result_1 = 0, result_2 = 0, result_3 = 0;

		for (int i = 1; i < 50; ++i)
		{
			DP(i);
			result_1 = dp[i];
			if (n < result_1) break;

			for (int j = 1; j < 50; ++j)
			{
				DP(j);
				result_2 = dp[j];
				if (n < result_1 + result_2) break;

				for (int k = 1; k < 50; ++k)
				{
					DP(k);
					result_3 = dp[k];
					if (n < result_1 + result_2 + result_3) break;

					if (result_1 + result_2 + result_3 == n)
					{
						pass = true;
						break;
					}
				}
				if (pass == true) break;
			}
			if (pass == true) break;
		}
		cout << (pass ? "1" : "0") << '\n';
	}
	return 0;
}

||사고 과정

먼저 가장 쉽게 생각 할 수 있는 완전 탐색이 가능한지 생각했다.

3중 for문으로 O(n^3)을 예상하여 n의 최대 값을 대략 구해보려했다.

구하려는 수k는 최대 1000이므로

1000 = n * (n + 1) / 2  → 2000 = n * (n + 1) 이다.

대략적으로 2000 = n^2이라 치면

n이 100일때 k는 10000

n이 50일때 k는 2500

고로 넉넉하게 n을 50이라 생각하면 50^3 = 125,000으로 1초안에 충분히 결과가 나올 수 있을것 같았다.

삼각수는 dp배열에 저장하여 다시 계산하지 않도록 연산을 생략했다.

||사용 기법

• Brute Force
• Dp

||다른 풀이

이건 백트래킹을 이용해 봤다.

#include <bits/stdc++.h>
using namespace std;

#define MAX 50
#define DP(x) if(dp[x] == 0) dp[x] = x * (x + 1) / 2

int dp[MAX];

//total:누적 값, i : 삼각수 번호, len : 재귀의 길이 (one index), n : 찾는 값
bool BT(int total, int i, int len, int n)
{
	if (3 < len) return false;
	
	DP(i);
	total += dp[i];
	if (total == n && len == 3) return true;
	if (n < total) return false;

	for (int k = 1; k < MAX; ++k)
	{
		if(BT(total, k, len + 1, n) == true) return true;
	}

	return false;
}

int main()
{
	ios::sync_with_stdio(0), cin.tie(0);
	int t; cin >> t;

	while (t--)
	{
		int n; cin >> n;
		cout << (BT(0,0,0,n) ? "1" : "0") << '\n';
	}
	return 0;
}

혹은 DP를 다 채우고 하는 사람도 많았다.

#include <bits/stdc++.h>
using namespace std;
#define MAX 50

int dp[MAX];

int main()
{
	ios::sync_with_stdio(0), cin.tie(0);
	int t; cin >> t;

	for (int i = 1; i < MAX; ++i)
	{
		dp[i] = i * (i + 1) / 2;
	}

	while (t--)
	{
		int n; cin >> n;

		bool pass = false;
		for (int i = 1; i < 50; ++i)
		{
			for (int j = 1; j < 50; ++j)
			{
				for (int k = 1; k < 50; ++k)
				{
					if (dp[i] + dp[j] + dp[k] == n) pass = true;
				}
			}
		}

		cout << (pass ? "1" : "0") << '\n';
	}
	return 0;
}

혹은 bool을 만들어서 아에 세가지가 될 수 있는 경우를 모두 저장하여 마지막에 바로바로 출력한다

여러 테스트 케이스가 있다면 이렇게 한번에 채우고 가는게 훨씬 좋은것 같다.

시간복잡도가 훨씬 줄어들었다.

내 생각엔 이 코드가 최고인것 같다.

#include <bits/stdc++.h>
using namespace std;
#define MAX 50

int dp[MAX];
bool b[125000];

int main()
{
	ios::sync_with_stdio(0), cin.tie(0);
	int t; cin >> t;

	for (int i = 1; i < MAX; ++i)
	{
		dp[i] = i * (i + 1) / 2;
	}
	
	for (int i = 1; i < MAX; ++i)
	{
		for (int j = 1; j < MAX; ++j)
		{
			for (int k = 1; k < MAX; ++k)
			{
				b[dp[i] + dp[j] + dp[k]] = true;
			}
		}
	}

	while (t--)
	{
		int n; cin >> n;
		cout << b[n] << '\n';
	}
	return 0;
}

이렇게 필요 없는 코드를 줄여보니까 어떻게 줄여야할지 좀 알았고 담에 좀 더 신경 써야겠다.

#include <iostream>

#define MAX 22
using namespace std;

int N, S;
int arr[MAX];

int result = 0;
void Solve(const int & total, const int & length, int level)
{
	if (1 <= level && total == S)
	{
		++result;
	}

	for (int i = length + 1; i < N; ++i)
	{
		Solve(total + arr[i], i, level + 1);
	}
}

int main()
{
	ios::sync_with_stdio(0), cin.tie(0);
	cin >> N >> S;

	for (int i = 0; i < N; ++i)
	{
		cin >> arr[i];
		if (arr[i] == S) ++result;
	}
	Solve(0, -1, -1);
	cout << result;
	return 0;
}

||사고 과정

처음엔 수열이 N개라면 N^4로 루프를 돌리면서 S에 맞는 값이면 카운트해서 풀이하려고 했다.

근데 쓸모없는 삽질을 통해 중복된 수열이 안된다는 것을 깨달았다..

그래도 이전 문제에서 시간을 줄이려고 하면서 이런 중복된걸 제외하는 코드가 생각나서 좀 쉽게 다가갈 수 있었다.

//중복포함
for(int i = 0; i < N; ++i)
{
	for(int j = 0; j < N; ++j)
	{
		cout << arr[i][j];
	}	
}

//중복제거
for(int i = 0; i < N; ++i)
{
	for(int j = i; j < N; ++j)
	{
		cout << arr[i][j];
	}	
}

이런 느낌인데 이걸 이번 문제에 대입하면

이렇게 볼 수 있다.

각 부모의 숫자보다 이하인 경우는 없다.

이를 이용하여 반복문을 돌려주었고 해결했다.

||사용 기법

• Back tracking

||풀면서 느낀 것

• 문제이해하기

문제만 계속 풀다보니까 집중력이 떨어져서 문제 파악을 잘 못했다.

생각해야할 예외도 많았는데 이 때문에 정말 많은 시간을 소모했다.

• 매개변수의 정확한 의미

length와 level을 두루뭉실하게 잡아놔서 헷갈리는 바람에 시간을 많이 소모함..

항상 단단한 설계가 시간을 아껴준다는걸 느낀다..

||더 나은 풀이

#include <stdio.h>

int a[20];

int n,m;
int cnt =0;

void f(int idx,int sum){
	if(sum==m) cnt++;
	for(int i=idx+1;i<n;i++) f(i,sum+a[i]);
}

int main(void){
	scanf("%d %d",&n,&m);
	for(int i=0;i<n;i++) scanf("%d",&a[i]);
	for(int i=0;i<n;i++) f(i,a[i]);
	printf("%d",cnt);
}

다른 분의 풀이인데 같은 방식이나 내 코드보다 훨씬 많이 최적화 됐다..

나도 풀이할 때 저렇게 for로 재귀를 돌려야하나 싶었는데

나는 메인에 한번만 호출해야한는 고정관념에 갇히고말았다..

담에는 더 분발해야겠다!

그리고 자기 부모인덱스보다 높은 인덱스만을 재귀로 진행했다면 

또 다른 코드는 각 인덱스를 더할지, 말지 로 재귀를 진행하는 코드도 있었다.

#include <iostream>

#define MAX 50
using namespace std;

int N;
int result = 0;
//b는 인덱스는 각 열의 위치를 의미한다.
//값은 이 열에 놓였는지를 뜻한다. true면 놓여있는 것
bool b1[MAX];
//값은 대각선'/'의 판별 식은 a + i
bool b2[MAX];
//값은 대각선'\'의 판별 식은 a - i + n //n을 더해주는것은 음수가 나오지 않게 하기 위해
bool b3[MAX];

void Solve(const int  & a)
{
	if (a == N)
	{
		result++;
		return;
	}

	//i가 어느 열위치에 놓이려고 하는지를 뜻함
	for (int i = 0; i < N; ++i)
	{
		if (b1[i] == true || b2[a + i] == true || b3[a - i + N] == true) continue;

		b1[i] = true;
		b2[a + i] = true;
		b3[a - i + N] = true;
		Solve(a + 1);
		b1[i] = false;
		b2[a + i] = false;
		b3[a - i + N] = false;
	}
}

int main()
{
	ios::sync_with_stdio(0), cin.tie(0);
	cin >> N;
	Solve(0);
	cout << result;
	return 0;
}

||사고 과정

연습하고 있는 백트래킹의 문제

처음에는 중복될수 있는게 많지 않을까? ,중복처리 다 할 수 없을거 같은데? 라는 생각으로 포기할뻔했다.

근데 몇가지 케이스를 직접 그리면서 해보니까 맨 위의 행을 반복하면 중복될 수가 없었다.

역시 뭐든 막연하면 한번 직접해봐야한다.. 안 했으면 포기했을뻔 했다.

암튼 그래서 한 행씩 내려오면서 검사를 하는데

여태 두었던 모든 퀸들의 열과 대각선을 검사해야할까? 해서 한 5까지는 시도해본결과

열은 다 검사하되 대각선은 바로 위의 퀸에만 검사해도 답이 나왔다.

하지만 이건 완전 잘못된 선택..

단지 맵이 작아서 우연히 맞았을 뿐이고 맵이커지면 규칙에 어긋난 배치도 카운팅 됐다.

이렇게 정확히 모를때는 한가지경우라도 범위가 큰 케이스에서 시도를 해보자

결국 한시간이 지나고 다른 사람의 코드를 보았다..

대각선 판별을 깔끔하게 하는걸 보고 놀랐다..

이건 잘 기억해 두어야겠다.

||사용 기법

• Back tracking 

||새로 알게 된것

• 대각선 판별

하나의 대각선' / ' 에 속하는 좌표는 X + Y값이 같다!

그 역 대각선은 X - Y 의 값이 같다!

단 X -Y 는 음수가 나올 수 있기에 배열에 대입하는 경우에는 고정 값을 더해주어야한다

뭔가 알게돼서 넘 좋았다ㅋㅋ

#include <iostream>
using namespace std;
typedef long long int ll;

int pre[16] = { 1,2,4,8,16,32,64,128,256,512,1024,2048,4096,8192,16384,32768 };

//0 : 좌측상단 , 1 : 우측상단, 2 : 좌측하단, 3 : 우측하단
int GetQuadrant(const bool & X, const bool & Y)
{
	if (X == true)
	{
		if (Y == true) return 3;
		else return 1;
	}
	else
	{
		if (Y == true) return 2;
		else return 0;
	}
}

ll Func(ll N, ll X, ll Y) 
{
	if (N == 0) return 0;

	//사분면 알아내기
	ll mid = pre[N] / 2;
	ll q = GetQuadrant(mid <= X, mid <= Y);

	//자기사각형에서의 최대값
	ll std = pre[N - 1] * pre[N - 1];
	ll max = std * q;

	//값 합쳐 반환
	return max + Func(N - 1, X % mid, Y % mid);
}

int main()
{
	ios::sync_with_stdio(0), cin.tie(0);
	ll N, Y, X; cin >> N >> Y >> X;
	
	cout << Func(N, X, Y);

	return 0;
}

||사고 과정

처음엔 진짜 뭔가 싶었던 1시간 5분 소요해서 풀은 문제...

일단 처음에 함수 형태를 생각했다.

int func(int n, int x, int y)
{
	return "x와 y좌표에 속하는 번호"
}

그리고 규칙을 찾았다.

처음엔 가로 몇번째 줄은 * 2하고  +2를 하고.. 세로는 뭐 어쩌구저쩌구 규칙이 있을까 하면서 생각했다.

그러던 중에 사각형이 4개 뭉텅이로 보이고 각 첫 숫자들이 보이게 됐다.

오 이렇게 16씩 더해지네 하다가 정말 기적처럼 결정적인 아이디어가 생각났다.

속한 사분면에 들어가서 다시 사분면으로 나누고 다시 사분면으로 나누고... 재귀적 아이디어였다.

예를 들어 밑의 별표는 저런식으로 4분면을 쪼개어 들어가는 것이였다.

그렇게 생각하게 된 함수는 이런식으로 변경했다.

int func(int n, int x, int y)
{
	return "2^n * 2^n인 사각형에서 최대로 가질수 있는 수"
}

이걸 생각하고 나서 문제 진행이 수월해졌고

이걸 재귀적으로 다시 수정하면

int func(int n, int x, int y)
{	
	if(n == 0) return 0;
	return "2^n * 2^n인 사각형에서 최대로 가질수 있는 수" + func (n - 1, x, y)
}

이러면 한 변이 2^n인 사각형에서 구할 수 있는 최대 수 + 2^n-1인 사각형에서 구할 수 있는 최대 수 ...

이런식으로 나오기 때문에 답을 구할 수 있겠다고 생각했다.

||사용 기법

• Recursive

||풀면서 느낀 것

• 모르겠을 때는 가만히 있지말고 뭐라도 해라

정말 이것저것 그리거나 규칙을 찾으려고 하지 않았으면 재귀적 아이디어도 떠오르지 않았을 것이다.

||나아 진것

• 재귀적 아이디어를 잘 찾은 것

재귀 문제를 많이 풀어보지 않았는데 혼자 이렇게 생각해 낸것에 대해 약간 뿌듯할지도...😎

개요

최장증가부분수열에 대해 공부하다가 이분탐색이 필요하게 되어 익히게 됐다.

특징

보통 선형탐색의 경우 O(N)이지만

이진 탐색은 계속 반씩 나누어 나머지 한쪽은 버리는 사이클을 이용하여 탐색을 진행하기 때문에

O(log N)으로 탐색이 가능하다.

단 단점은 정렬된 컨테이너에서만 가능하다.

또한 정확히 반으로 나누지 않을 경우 무한 루프에 빠지는 경우가 있다.

왜 사용하는가?

선형 탐색보다 빠른 속도로 탐색을 진행하려고!

구현

Binary search

int BinarySearch(const int * arr, const int & size, const int & f)
{
	int s = 0, e = size, m;

	while (s <= e)
	{
		m = (s + e) / 2;

		//중앙 값이 찾는 값인지 확인
		if (arr[m] == f) return m;

		//시작 or 끝 인덱스 조정
		if (arr[m] < f) s = m + 1;
		else e = m - 1;
	}
	return -1;
}

시작 인덱스(s), 중앙 인덱스(m), 끝 인덱스(e) 를 의미하는 정수형 변수로 돌아가게 된다.

m은 항상 (s + e) / 2 로 구할 수 있고

m이 찾는 값보다 크다면 끝 지점을 m으로 옮기고

m이 찾는 값보다 작다면 시작 지점을 m으로 옮긴다.

이렇게 진행하다보면 어느 순간 s와 e가 겹치게 되는데

이때 끝내버리면 m이 s와 e가 겹친 인덱스를 한번도 찾지 못하게 되어서

while ( s < e ) 가 아닌 while ( s <= e ) 를 사용했다.

그 후 교차가 되어서 교차가 되면 끝나고 찾지 못했다는 의미로 -1을 반환하는 형식으로 구현했다.

#include <iostream>
#include <algorithm>

#define MAX 1'000'002
using namespace std;

pair<int, int> arr[MAX];

bool comp(const pair<int, int> & a, const pair<int, int> & b)
{
	return a.second < b.second;
}

int main()
{
	ios::sync_with_stdio(0), cin.tie(0);

	int N; cin >> N;

	for (int i = 0; i < N; ++i)
	{
		cin >> arr[i].first;
		arr[i].second = i;
	}
	sort(arr, arr + N);

	int std = 0;
	for (int i = 0; i < N; ++i)
	{
		//바로 오른쪽이 자신과 같은지 
		if (arr[i].first == arr[i + 1].first) arr[i].first = std;
		else arr[i].first = std++;
	}
	sort(arr, arr + N, comp);
	
	for (int i = 0; i < N; ++i)
	{
		cout << arr[i].first << " ";
	}
		
	return 0;
}

||사고 과정

문제의 Xi를 좌표 압축한 결과 X'i의 값은 Xi > Xj를 만족하는 서로 다른 좌표의 개수와 같아야 한다.

는 말이 이해하기 힘들었지만 그냥 최소값부터 압축하라는 뜻..

Upper bound, Lower bound를 공부하면서 보게 된 문제여서 처음에는 Upper bound를 이용해서 풀려고했지만

1, 2, 3, 4, 5 처럼 중복되는 수가 없는 경우면 매 수마다 Upper bound를 하게 되니까 비효율적이라 생각해서

바로 옆에 있는 수를 비교해서 압축하는게 오히려 나을 수도 있겠다고 생각이 들어서 이렇게 풀게 됐다.

||더 나은 풀이

#include <iostream>
#include <algorithm>

#define MAX 1'000'002
using namespace std;

pair<int, int> arr[MAX];
int result[MAX];

bool comp(const pair<int, int> & a, const pair<int, int> & b)
{
	return a.second < b.second;
}


int main()
{
	ios::sync_with_stdio(0), cin.tie(0);

	int N; cin >> N;

	for (int i = 0; i < N; ++i)
	{
		cin >> arr[i].first;
		arr[i].second = i;
	}
	sort(arr, arr + N);

	int std = 0; 
	for (int i = 1; i < N; ++i)
	{
		if (arr[i].first != arr[i - 1].first) ++std;
		result[arr[i].second] = std;
	}
	
	for (int i = 0; i < N; ++i)
	{
		cout << result[i]<< " ";
	}
		
	return 0;
}

다른 사람들의 코드를 보던 중에 내 코드에서 sort한번을 생략 할 수 있음을 알았다.

배열을 하나 더 추가해서 arr[i]의 원래 순서의 인덱스에 넣는 방법이였다.

=> result[arr[i[.second] = std;

다른 문제에서 이렇게 원래 순서를 sort해서 가져오는 경우가 종종있었는데 앞으로 좀 더 빠르게 구현할 수 있겠다.

추가로 lower_bound를 이용해 푸는 방법으로 바킹독님 코드를 빌려왔다.

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

int n;
int x[1000005];
vector<int> uni; // unique
int main(void) {
	ios::sync_with_stdio(0);
	cin.tie(0);

	cin >> n;
	for (int i = 0; i < n; i++) {
		cin >> x[i];
		uni.push_back(x[i]);
	}
	sort(uni.begin(), uni.end());
	uni.erase(unique(uni.begin(), uni.end()), uni.end());
	for (int i = 0; i < n; i++)
		cout << lower_bound(uni.begin(), uni.end(), x[i]) - uni.begin() << ' ';
}

정렬 후 중복제거를 하게 되면 각 인덱스가 좌표압축한 결과와 같아진다.

ex) 

원본 배열 : [3] [2] [3] [3] [2] [4]

정렬 후 중복제거 : [2] [3] [4]

여기서 [2]는 인덱스가 0으로 2를 좌표압축한 결과와 같고 3, 4 도 마찬가지다.

이분탐색은 인덱스의 위치를 알 수 없으니 lower_bound로 그 위치를  알아내서 풀이하는 방법

개요

이분 탐색문제를 풀이하다 나온 개념

특징

이분 탐색을 응용한 알고리즘으로

정렬된 수열에서 찾고자 하는 값들의의 첫인덱스, 마지막 인덱스 + 1 을 구할 수 있다.

왜 사용하는가?

경험상 적절한 위치를 알기 위해서 사용하는 것 같다.

Lower bound는 찾고자 하는 값 이상의 부분수열에서 첫번째 인덱스

Upper bound는 찾고자 하는 값을 초과하는 부분수열에 첫번째 인덱스

이 위치들의 특징은 이곳에 찾고자 하는 값을 삽입해도 오름차순이 유지되는 특징이있다.

그리고 Upper bound -  Lower bound 의 값은 그 안에 속한 원소의 개수도 구할 수 있다.

구현

Lower bound

int Lower_bound(const int * arr, const int & size, const int & f)
{
	int s = 0, e = size, m;
	while (s < e)
	{
		m = (s + e) / 2;

		if (f <= arr[m]) e = m;
		else s = m + 1;
	}

	return s;
}

Lower bound는 f 가 시작 되는 지점을 찾는게 목표이다.

고로

시작지점은 arr[s] <= f, 끝 지점은 f <= arr[e] 라는 조건이 붙는다.

f <= arr[m] 일때 이 조건과 같은 e를 m에 두고 

나머지 경우인 arr[m] < f 는 해당되는 s를 m의 위치에 두되,

그냥 두면 s가 f에 도달하지 못하므로 m + 1인 인덱스를 s에 부여해준다.

Upper bound

int Upper_bound(const int * arr, const int & size, const int & f)
{
	int s = 0, e = size, m;
	while (s < e)
	{
		m = (s + e) / 2;

		if (f < arr[m]) e = m;
		else s = m + 1;
	}

	return e;
}

Upper bound는 f 가 끝나는 지점 + 1 을 찾는게 목표이다.

고로

시작지점은 arr[s] <= f, 끝 지점은 f < arr[e] 라는 조건이 붙는다.

f < arr[m] 일때 이 조건과 같은 e를 m에 둔다면 f와 arr[e]는 같은 값이 될수 없으며

나머지 경우인 arr[m] <= f 는 위으 Lower bound와 같다.