백준 1059번 - 좋은 구간

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

1059번: 좋은 구간

사고과정)

1. 우선 입력받은 값들을 오름차순으로 정렬한다

2. 입력받은 값(target)을 기점으로 바로 왼쪽값을 small, 바로 오른쪽값을 big이라 하고 이를 반복문으로 하나씩 접근하면서 할당.

3. 예제 2번의 경우 target = 10 이므로 small = 8, big = 13이 나온다. 하지만 해당 배열 안의 값은 들어가면 안되므로

small++, big--을 해준다.

그러면 small = 9, big = 12이다.

해당 경우들은 (9,10) (9,11) (9,12) (10, 11) (10, 12)이다.

이를 토대로

 

int cnt = 0;
	while (small <= target)
	{
		cnt += (big - target + 1);
		if (small == target)
			--cnt;
		small++;
	}

를 구현할 수 있다. 마지막에 target == small 이 된다면, (10,10) 이 경우는 해당이 안되므로 -1을 해준다.

 

정답 코드)

#include <iostream>
#include <algorithm>
using namespace std;

int main()
{
	int N = 0;
	cin >> N;
	int arr[50];
	for (int i = 0; i < N; i++)
		cin >> arr[i];

	std::sort(arr, arr + N);
	int target = 0;
	cin >> target;

	int small = 0, big = 0;
	for (int i = 0; i < N; i++)
	{
		if (arr[i] < target)
			small = arr[i];
		else if (arr[i] > target) 
		{
			big = arr[i];
			break;
		}
		else // arr[i] == target
		{
			cout << 0 << endl;
			return 0;
		}
	}
	small++;
	big--;

	int cnt = 0;
	while (small <= target)
	{
		cnt += (big - target + 1);
		if (small == target)
			--cnt;
		small++;
	}
	
	cout << cnt;
	return 0;
}