(BOJ) 15790 최종병기 활

문제: https://www.acmicpc.net/problem/15790

 

문제 풀이: 

활의 길이를 기준으로 이분 탐색

(mid=활의 길이)

어떤 홈을 기준으로 시작해서 다음 홈까지의 길이가 mid 이상이면 그 곳을 절단하고,

또, 그 곳부터 길이가 mid 이상인 홈을 만나면 절단.

3겹으로 만든다고 하면, 맨 처음에 시작 점은 이미 골라져 있으므로 2개를 더 찾아 자르고,

마지막 점에서 처음 절단한 곳까지의 길이 또한 mid 이상이면 활의 길이는 mid로 만들 수 있다

주의할 점은, 시작하는 점이 항상 맨 처음 홈이 아닐 수도 있으므로 모든 홈을 처음 홈으로 설정하고 

작업 해준다.

 

 

* 헤헷 남들은 8~40ms 걸리는데 난 104ms나 걸리넹 ㅎㅎ

 

소스 코드:

int n, m, k;
vector<int> v;

bool func(int cur, int cnt,int sz,int f) {
	int i = (cur + 1)%m;
	
	while (i!=f) {
		if ((v[i] - v[cur]+n)%n >= sz) {
			cur = i;
			cnt++;
			if (cnt == k) {
				if ((v[f] - v[cur] + n) % n >= sz) return true;
				return false;
			}
		}
		i=(i+1)%m;
	}

	return false;
}
int main()
{
	ios::sync_with_stdio(false);
	cin.tie(NULL), cout.tie(NULL);

	cin >> n >> m >> k;
	for (int i = 0; i < m; i++) {
		int a;
		cin >> a;
		v.push_back(a);
	}
	if (k == 1) {
		cout << n << '\n';
		return 0;
	}
	int l = 1, r =n;
	while (l <= r) {
		int mid = (l + r) >> 1;
		bool chk = false;
		for (int i = 0; i < m; i++) {
			if (func(i, 1, mid,i)) {
				chk = true;
				break;
			}
		}
		if (chk) l = mid + 1;
		else r = mid - 1;
	}
	cout << r << '\n';
	return 0;
}